数据结构c语言版 (6)

《数据结构c语言版 (6)》由会员分享，可在线阅读，更多相关《数据结构c语言版 (6)（38页珍藏版）》请在金锄头文库上搜索。

1、第第 六六 章章 图图退出退出图论起源哥尼斯堡七桥问题 图的定义图的定义图是由结点的有穷集合V和边的集合 E组成。其中，为了与树形结构加以区 别，在图结构中常常将结点称为顶点， 边是顶点的有序偶对，若两个顶点之间 存在一条边，就表示这两个顶点具有相 邻关系。6 61 1基本概念和术语基本概念和术语在有向图中，通常将边称作弧，含箭头的一端 称为弧头，另一端称为弧尾，记作，它表示 从顶点vi到顶点vj有一条边。若有向图中有n个顶点，则最多有n(n-1)条弧 ， 我们又将具有n(n-1)条弧的有向图称作有向完全 图。以顶点v为弧尾的弧的数目称作顶点v的出度， 以顶点v为弧头的弧的数目称作顶点v的入度

2、。 在无向图中，边记作(vi,vj)，它蕴涵着存在和两条弧。若无向图中有n个顶点，则 最多有n(n-1)/2条边，我们又将具有n(n-1)/2条边的 无向图称作无向完全图。与顶点v相关的边的条数称作顶点v的度。路径长度是指路径上边或弧的数目。若第一个顶点和最后一个顶点相同，则这条路径 是一条回路。 若路径中顶点没有重复出现，则称这条路径为 简单路 径。在无向图中，如果从顶点vi到顶点vj有路径，则称vi 和vj连通。如果图中任意两个顶点之间都连通，则称该 图为连通图，否则，将其中的极大连通子图称为连通分 量。在有向图中，如果对于每一对顶点vi和vj，从vi到vj 和从vj到vi都有路径，则称该

3、图为强连通图；否则，将 其中的极大连通子图称为强连通分量。图的存储结构图的存储结构l邻接矩阵带权图l邻接列表Struct Node int vertex;struct Node *Next; graph;邻接顶点下一邻接顶点6.3 6.3 图的遍历图的遍历l常见的图遍历方式有两种：深度优先遍 历和广度优先遍历，这两种遍历方式对 有向图和无向图均适用。深度优先遍历深度优先遍历深度优先遍历的思想类似于树的先序遍 历。其遍历过程可以描述为：从图中某个顶点v出发，访问该顶 点，然后依次从v的未被访问的邻接点 出发继续深度优先遍历图中的其余顶点 ，直至图中所有与v有路径相通的顶点 都被访问完为止。广度优

4、先遍历广度优先遍历对图的广度优先遍历方法描述为：从图 中某个顶点v出发，在访问该顶点v之后 ，依次访问v的所有未被访问过的邻接 点，然后再访问每个邻接点的邻接点， 且访问顺序应保持先被访问的顶点其邻 接点也优先被访问，直到图中的所有顶 点都被访问为止。练习练习分别列出以1、8为起点的深度优先遍历以及广度优先遍历的序列6.4 6.4 最小生成树问题最小生成树问题对于一个拥有n个顶点的无向连通图，它的边数一定多于n-1条。若从中选择n-1条边，使得无向图仍然连通，则由n个顶点及这 n-1条边（弧）组成的图被称为原无向图的生成树。l深度优先遍历l广度优先遍历最小生成树最小生成树1.Kruskal 算

5、法根据边的权值以递增的方式，依次找 出权值最小的边来建立最小生成树， 且规定每次添加的边不能造成生成树 有回路，直到找到n-1条边为止。2. Prim算法以开始时生成树的集合为起始的顶点， 然后找出与生成树集合邻接的边中，权 值最小的边建立生成树，为了确定新加 入的边不会造成回路，所以每一个新加 入的边，只允许有一个顶点在生成树集 合中，重复执行此步骤，直到找到n-1 条边为止。练习练习3527644639分别用两种算法建立最小生成树6.56.5最短路径最短路径1.从某个源点到其余各顶点的最短路Dijkstra算法规则：（类似Prim算法）将起始顶点插入树中找出树中所有该顶点的邻接边中，总和

6、最小的边重复，直到所有的顶点都在树中为止 。35276 446396.56.5最短路径最短路径2.每一对顶点间的最短路径弗洛伊德算法A(-1)ij=Edgeij;A(K) ij=minA(K-1)ij, A(K-1) ik+ A(K-1) kj k=0、1n-1 12 59 43686 66 6 拓扑排序拓扑排序拓扑排序是有向图的一个重要操作。在 给定的有向图G中，若顶点序列 vi1,vi2,.,vin满足下列条件：若在有向图G 中从顶点vi到顶点vj有一条路径，则在 序列中顶点vi必在顶点vj之前，便称这 个序列为一个拓扑序列。求一个有向 图拓扑序列的过程称为拓扑排序。举例：计算机专业的学生

7、应该学习的部分课程及其每门 课程所需要的先修课程。拓扑排序的方法： （1）从图中选择一个入度为0的顶点且输出之 ； （2）从图中删掉该顶点及其所有以该顶点为 弧尾的弧；反复执行这两个步骤，直到所有的顶点都被 输出，输出的序列就是这个无环有向图的拓 扑序列。算法实现的基本过程： 将所有入度为0的顶点入栈；当栈非空时重复执行下列操作：从栈中退出顶点k；（1）将k顶点的信息输出；（2）将与k邻接的所有顶点的入度减1。习题习题l已知一个图如图所示，若从顶点a出发按深度搜索法进行遍历， 则可能得到的一种顶点序列为_；按广度搜索法进行遍历， 则可能得到的一种顶点序列为_。l A. a,b,e,c,d,f

8、B. a,c,f,e,b,d C. a,e,b,c,f,d D. a,e,d,f,c,bl A. a,b,c,e,d,f B. a,b,c,e,f,d C. a,e,b,c,f,d D. a,c,f,d,e,bl已知一有向图的邻接表存储结构如图所示 。 根据有向图的深度优先遍历算法，从顶点v1 出发， 所得到的顶点序列是_。 A. v1,v2,v3,v5,v4 B. v1,v2,v3,v4,v5 C. v1,v3,v4,v5,v2 D. v1,v4,v3,v5,v2 根据有向图的广度优先遍历算法，从顶点v1 出发，所得到的顶点序列是_。 A. v1,v2,v3,v4,v5 B. v1,v3,v2,v4,v5 C. v1,v2,v3,v5,v4 D. v1,v4,v3,v5,v2l试列出下图中全部的拓扑排序序列。l求从顶点a到其余各顶点之间的最短路径和所 有顶点对之间的最短路径。