资源描述：
《数据结构第5章 图》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第5章图（一）课程内容5.1图的概念5.2图的存储结构5.3图的遍历5.4生成树和最小生成树5.5最短路径5.6拓扑排序（二）学习目的与要求本章的目的图的基本概念、两种常用的存储结构、两种遍历算法以及图的应用算法。本章重点是掌握在图的两种存储结构上实现的遍历算法。本章难点是图的应用算法：求最小生成树，求最短路径以及拓扑排序，只要求考生掌握这些算法的基本思想及时间性能。（三）考核知识点与考核要求1.图的概念，要求达到“领会”层次。1.1图的逻辑结构特征。1.2图的常用术语及含义。2.图的存储结构，要求达到“简单应用”层次。2.1邻接矩阵和邻接表这两种存储结构的特点及适
2、用范围。2.2根据应用问题的特点和要求选择合适的存储结构。3.图的遍历，要求达到“简单应用”层次。3.1连通图及非连通图的深度优先搜索和广度优先搜索两种遍历算法,其执行过程以及时间分析。3.2确定两种遍历所得到的顶点访问序列。3.3图的两种遍历与树的遍历之间的关系。3.4两种遍历所使用的辅助数据结构（栈或队列）在遍历过程中所起的作用。3.5利用图的两种遍历设计算法解决简单的应用问题。（三）考核知识点与考核要求4.生成树和最小生成树，要求达到“领会”层次。4.1生成树和最小生成树的概念。4.2对遍历给定的图，画出深度优先和广度优先生成树或生成森林。4.3 Prim和K
3、ruskal算法的基本思想、时间性能及这两种算法各自的特点。4.4要求对给定的连通图，根据Prim和Kruskal算法构造出最小生成树。5.最短路径，要求达到“领会”层次。5.1最短路径的含义。5.2求单源最短路径的Dijkstra算法的基本思想和时间性能。5.3对于给定的有向图，根据Dijkstra算法画出求单源最短路径的过程示意图。6.拓扑排序，要求达到“领会”层次。6.1拓扑排序的基本思想和步骤。6.2拓扑排序不成功的原因。6.3对给定的有向图，若拓扑序列存在，则要求写出一个或多个拓扑序列。5.1图的概念图(Graph)是一种复杂的非线性结构，在图结构中，对结
4、点的前驱和后继的个数没有任何限制，结点之间的关系是任意的，图中任意两个结点之间都可能有关系。图结构在计算机科学、人工智能、工程、数学、物理等领域中，有着广泛的应用。一、图的二元组定义定义：图G由两个集合V和E组成,记为：G=(V，E)其中：V是有限的非空集合，V中的元素称为顶点或结点，E是V中顶点偶对(vi,vj)的集合，E中的元素称为边。说明：图G的顶点集和边集也可记为V(G)和E(G)。E(G)可以是空集，若为空，则图G只有顶点没有边；图中的边(vi,vj)描述了两个顶点之间是相关的。二、无向图和有向图1、无向图：若图G中的每条边都是没有方向的，则称G为无向图。
5、无向图中边的表示：无向图中的边均是顶点的无序对，无序对通常用圆括号表示，无序对(vi,vj)和(vj,vi)表示图中的同一条边。2、有向图：若图G中的每条边都是有方向的，则称G为有向图。有向图中边的表示：有向图中的边是由顶点的有序对组成，有序对通常用尖括号表示，有序对和表示的是图中不同的边。有向边也称为弧，边的始点称为弧尾，终点称为弧头。说明：①若(v1，v2)或是E(G)中的一条边，则要求v1≠v2；②不允许一条边在图中重复出现；③不允许在同一个图中既有有向边又有无向边。例如：下图G1是无向图，该图的顶点集和边集分别为：V
6、(G1)={v1,v2,v3,v4}E(G1)={(v1,v2),(v1,v3),(v2,v3),(v3,v4)}图G1v1v2v3v4例如：下图G2是有向图，该图的顶点集和边集分别为：V(G2)={v1,v2,v3}E(G2)={,,}图G2v1v2v363、完全图①无向完全图：若G是具有n个顶点e条边的无向图，则顶点数与边数的关系为0≤e≤n(n-1)/2。把恰有n(n-1)/2条边的无向图称为无向完全图。②有向完全图：若G是具有n个顶点e条边的有向图，则顶点数与边数的关系为0≤e≤n(n-1)。把恰有n(n-1)条边的
7、有向图称为有向完全图。说明：完全图具有最多的边数。任意一对顶点间均有边相连。三、图的边和顶点的关系1、无向边和顶点关系若(vi,vj)是一条无向边，则称顶点vi和vj互为邻接顶点，或称vi和vj相邻接；并称(vi,vj)依附或关联于顶点vi和vj，或称(vi,vj)与顶点vi和vj相关联。例如：下图G3是一个具有4个顶点的无向完全图。图G3v1v2v3v42、有向边和顶点关系若是一条有向边，则称顶点vi邻接到vj，顶点vj邻接于顶点vi；并称边关联于vi和vj或称与顶点vi和vj相关联。3．顶点的度①无向图中顶点v的度：
