数据结构 第6章 图

1、数据结构 与 算法,第七讲：图,开场白,08/07/2020,2,内容提要,图的定义 图的存储结构 图的遍历 最小生成树 最短路径 拓扑排序 关键路径,08/07/2020,3,图的定义,08/07/2020,4,图(Graph)是由顶点的有穷集合和顶点之间的边的集合组成，通常表示为：G(V,E)，其中 G 表示一个图，V 是图 G 中顶点的集合，E 是图 G 中边的集合。,1,2,3,5,7,6,9,8,4,图的术语（一）,图按有无方向分为无向图和有向图。无向图由顶点和边构成，有向图由顶点和弧构成。弧有弧头和弧尾之分。 图按照边或弧的多少分稀疏图和稠密图。如果任意两个顶点之间都存在边叫完全图

2、，有向的叫有向完全图。若无重复的边或顶点到自身的边则叫简单图。 图中顶点之间有邻接点、依附的概念。无向图顶点的边数叫做度，有向图顶点分为入度和出度。 图上的边或弧上带权则称为网。,08/07/2020,5,A,B,D,C,A,B,D,C,A,B,D,C,北京,香港,上海,台北,1463,1680,1200,808,700,2160,图a,图b,图c,图d,图的术语（二）,08/07/2020,6,图中顶点存在路径，两顶点存在路径则说明是连通的，如果路径最终回到起始点则称为回路或环，当中不重复叫简单路径。若任意两顶点都是连通的，则图就是连通图，有向则称强连通图。图中有子图，若子图极大连通则就是连

3、通分量，有向则称强连通分量。,A,B,D,C,A,B,D,C,图a,图b,图c,思考1：图b是强连通图吗?图c呢？,A,D,C,A,B,D,C,图f,E,F,A,B,C,图d,E,F,图e,思考2：图d是图f的连通分量吗？,图的术语（三）,08/07/2020,7,无向图中连通且n个顶点n-1条边叫生成树。有向图中一顶点入度为0其余顶点入度为1的叫有向树。一个有向图由若干棵有向树构成生成森林。,A,B,D,C,图a,F,E,G,H,A,B,D,C,图b,F,E,G,H,图的抽象数据类型,08/07/2020,8,ADT 图（Graph） Data 顶点的有穷集合和边的集合。 Operation

4、 CreateGraph( typedef int EdgeType; #define MAXVEX 100 #define INFINITY 65535 typedef struct VertexType vexsMAXVEX; EdgeType arcMAXVEXMAXVEX; int numVertexes, numEdges; MGraph; void CreateMGraph(MGraph G) int i, j, k, w; printf(输入顶点数和边数：n); scanf(%d,%d, ,时间复杂度：O(n+n2+e),思考：邻接矩阵的缺点？,图的存储结构：邻接表（一）,邻接表

5、：一维数组存顶点（包括数据和指向第一个邻接点的指针），每个顶点vi的所有邻接点构成一个单链表,08/07/2020,13,思考：如何知道某结点的度？ 如何判断某条边是否存在？ 如何求一个顶点的所有邻接点？,图的存储结构：邻接表（二）,08/07/2020,14,V0,V4,V1,V3,V2,9,有向网图,typedef char VertexType; typedef int EdgeType; typedef struct EdgeNode int adjvex; EdgeType weight; struct EdgeNode *next; EdgeNode; typedef struct

6、 VertexNode VertexType data; EdgeNode *firstedge; VertexNode, AdjListMAXVEX; typedef struct AdjList adjList; int numVertexes, numEdges; GraphAdjList;,下标,0,1,2,3,4,0,V0,V1,V2,V3,data,firstedge,adjvex,next,0,3,4,4,V4,6,9,2,1,5,2,3,weight,图的存储结构：邻接表（三）,08/07/2020,15,void CreateALGraph(GraphAdjList / 将当

7、前顶点的指针指向e ,时间复杂度：O(n+e),图的存储结构：十字链表,十字链表：有向图的优化，把邻接表和逆邻接表结合起来。,08/07/2020,16,V0,V3,V2,V1,有向图,下标,0,1,2,3,3,0,V0,V1,V2,V3,data,firstedge,adjvex,next,2,0,1,创建算法的时间复杂度：O(n+e),注意：虚线箭头其实就是逆邻接表的表示,图的存储结构：邻接多重表,邻接多重表：无向图的优化，原来用两个结点表示的一条边，现在用一个结点表示,08/07/2020,17,V0,V3,V2,V1,无向图,下标,0,1,2,3,1,2,0,V0,V1,V2,V3,d

8、ata,firstedge,adjvex,next,3,2,0,1,3,0,2,图的存储结构：边集数组,边集数组：两个一维数组。一个存储顶点的信息；另一个存储边的信息，边数组每个数据元素由一条边的起点下标（begin）、终点下标（end）和权（weight）组成。,08/07/2020,18,V0,V4,V1,V3,V2,9,V0,V1,V2,V3,顶点数组,V4,有向网图,边数组,typedef struct int begin; int end; int weight; Edge;,内容提要,图的定义 图的存储结构 图的遍历 最小生成树 最短路径 拓扑排序 关键路径,08/07/2020,

9、19,图的遍历,你经常找不到钥匙吗？ 图的遍历 从图中某一顶点出发 访遍图中其余顶点， 且使每一个顶点仅被 访问一次 两种方法： 深度优先遍历 广度优先遍历,08/07/2020,20,你玩游戏的时候讨厌走迷宫吗？,深度优先遍历(Depth First Search),08/07/2020,21,A,B,F,G,H,E,D,I,C,A,B,C,A,D,E,F,G,H,I,从图中某个顶点v出发，访问此顶点，然后从v的未访问的邻接点出发，深度优先遍历图，直至图中所有和v有路径相同的顶点都被访问到。对于非连通图，则需要对它的连通分量分别进行深度优先遍历。,注意：是否与树的某个次序遍历相似？,邻接矩阵

10、结构的深度优先遍历实现,08/07/2020,22,#define TRUE 1 #define FALSE 0 typedef int Boolean; /* Boolean是布尔类型，其值是TRUE或FALSE */ Boolean visitedMAX; /* 访问标志的数组 */ /* 邻接矩阵的深度优先递归算法 */ void DFS(MGraph G, int i) int j; visitedi = TRUE; printf(%c , G.vexsi); /* 打印顶点，也可以为其他操作 */ for (j=0; jG.numVertexes; j+) if (G.arcij =

11、 1 ,时间复杂度：O(n2),邻接表结构的深度优先遍历实现,08/07/2020,23,/* 邻接表的深度优先递归算法 */ void DFS(GraphAdjList GL, int i) EdgeNode *p; visitedi = TRUE; printf(%c , GL.adjListi.data); /* 打印顶点，也可以是其他操作 */ p = GL.adjListi.firstedge; while (p) if (!visitedp-adjvex) DFS(GL, p-adjvex); /* 对未访问的邻接顶点递归调用 */ p = p-next; /* 邻接表的深度优先遍

12、历操作 */ void DFSTraverse(GraphAdjList GL) int i; for (i=0; iGL.numVertexes; i+) visitedi = FALSE; /* 初始化所有顶点状态，都是未访问过状态 */ for (i=0; iGL.numVertexes; i+) if(!visitedi) /* 对未访问过的顶点调用DFS，若是连通图，只会执行一次 */ DFS(GL, i); ,时间复杂度：O(n+e),广度优先遍历(Breath First Search),08/07/2020,24,A,B,F,G,H,E,D,I,C,A,B,F,G,H,E,D,

13、I,C,F,C,I,G,A,B,F,C,I,G,E,E,D,H,D,I,G,E,D,H,G,E,D,H,(1),(2),(3),(4),(5),(6),(7),(8),(9),出队列,入队列,邻接矩阵结构的广度优先遍历实现,08/07/2020,25,void BFSTraverse(MGraph G) /* 邻接矩阵的广度优先遍历算法 */ int i, j; Queue Q; for (i=0; iG.numVertexes; i+) visitedi = FALSE; InitQueue( ,时间复杂度：O(n2),邻接表结构的广度优先遍历实现,08/07/2020,26,void BF

14、STraverse(GraphAdjList GL) /* 邻接表的广度优先遍历算法 */ int i; EdgeNode *p; Queue Q; for (i=0; iadjvex) /* 若此顶点未被访问 */ visitedp-adjvex = TRUE; printf(%c , GL.adjListp-adjvex.data); EnQueue( /* 指针指向下一个邻接点 */ ,时间复杂度：O(n+e),深度优先 vs 广度优先,如果存储结构一样，时间复杂度是一样的 应用场景：深度优先更适合找目标，广度优先更适合在不断扩大遍历范围时找到相对最优解。 方法论：深度优先或广度优先是一

15、种生活态度 博览群书不求甚解，还是专攻一门深入钻研？ 走马观花蜻蜓点水，还是寻幽探奇深度体验？ 四海之内皆兄弟，还是人生的一知己足矣？,08/07/2020,27,内容提要,图的定义 图的存储结构 图的遍历 最小生成树 最短路径 拓扑排序 关键路径,08/07/2020,28,最小生成树(Minimum Cost Spanning Tree),假设你是电信工程师，需要为一个镇子的九个村庄架设通信网络 v0-v8是村庄 连线上的数字表示村与村之间的距离 没有连线的表示不可直达，比如中间有高山或湖泊,08/07/2020,29,V0,V5,V4,V7,V6,V1,V2,V8,V3,11,10,18

16、,16,17,26,19,24,12,21,22,8,16,20,7,最小生成树：普里姆(Prim)算法过程及演示,假设N=(V,E)是连通网，TE是N上最小生成树中边的集合。算法从U=u0(u0V),TE=开始。重复执行下述操作：在所有uU,vV-U的边(u,v)E中找一条代价最小的边(u0,v0)并入集合TE，同时v0并入U，直至U=V为止。此时TE中必有n-1条边，则T=(U,TE)为N的最小生成树。 算法演示： U 包含所有蓝灰色的结点； V-U 包含所有白色的结点； E 包含所有蓝灰色的边； TE 包含所有红色的边。,08/07/2020,30,V0,V5,V4,V7,V6,V1,V

17、2,V8,V3,11,10,18,16,17,26,19,24,12,21,22,8,16,20,7,最小生成树：普里姆(Prim)算法代码实现,08/07/2020,31,void MiniSpanTree_Prim(MGraph G) int min, i, j, k; / 保存已访问的距离最近邻接结点的下标 int adjvexMAXVEX; /* 保存已访问的距离最近的邻接结点之间的权值 */ int lowcostMAXVEX; /* lowcost为0表示该下标的顶点已加入生成树,一开始生成树中仅有v0 */ lowcost0 = 0; adjvex0 = 0; for (i=1;

18、 iG.numVertexes; i+) /* 将其他结点与v0之间的权值存入lowcost数组 */ lowcosti = G.arc0j; adjvexi = 0; for(i=1; iG.numVertexes; i+) /* 依次将其余结点加入最小生成树，具体操作见右边代码 */ ,min = INFINITY; j = 1; k = 0; while (jG.numVertexes) if (lowcostj!=0 ,适用于稠密图，时间复杂度：O(n2),最小生成树：克鲁斯卡尔(Kruscal)算法过程演示,假设N=(V,E)是连通网，令最小生成树的初始状态只有n个顶点而无边的非连通

19、图T=(V,)，图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上（即加上该边不会形成回路），则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。以此类推，直至T中所有顶点都在同一连通分量上为止。 算法演示： E 包含所有浅色的边； T 包含所有红色的边； 黑色的边为舍去的边。,08/07/2020,32,V0,V5,V4,V7,V6,V1,V2,V8,V3,11,10,18,16,17,26,19,24,12,21,22,8,16,20,7,最小生成树：克鲁斯卡尔(Kruscal)算法代码实现,08/07/2020,33,void MiniS

20、panTree_Kruskal(MGraph G) int i, n, m; Edge edgesMAXEDGE; int parentMAXVEX; /* 此处省略将邻接矩阵G转化为边集数组edges并按权由小到大排序的代码 */ for (i=0; i0) f = parentf; return f; ,适用于稀疏图，时间复杂度：O(eloge),0,0,0,0,0,0,0,0,0,0,1,2,3,4,5,6,7,8,7,8,1,5,8,7,6,7,内容提要,图的定义 图的存储结构 图的遍历 最小生成树 最短路径 拓扑排序 关键路径,08/07/2020,34,最短路径,08/07/202

21、0,35,网图:指两顶点之间经过的边上权值之和最少的路径。 非网图：指两顶点之间经过的边数最少的路径。 源点 终点,迪杰斯特拉(Dijkstra)算法,用途：求某个源点到其余各顶点的最短路径 思路：按路径长度递增的次序产生最短路径 算法演示：,08/07/2020,36,V1,V2,V3,V4,V5,V0,V6,V7,V8,1,5,7,5,3,1,7,3,2,3,6,9,5,2,7,4,下一个离v0最近的点是v1， 下一个离v0最近的点是v2， 下一个离v0最近的点是v4， 下一个离v0最近的点是v3， 下一个离v0最近的点是v5， 下一个离v0最近的点是v6， 下一个离v0最近的点是v7，

22、下一个离v0最近的点是v8，,v0v1v2v4v3v6v7v8,v0到v8的最短路径是,迪杰斯特拉(Dijkstra)算法代码实现,08/07/2020,37,#define MAXVEX 9 #define INFINITY 65535 typedef int PathMatrixMAXVEX; typedef int ShortPathTableMAXVEX; /* Pv的值为前驱顶点的下标 */ /* Dv表示v0到v的最短路径长度和 */ void SP_Dijkstra(MGraph G, int v0, PathMatrix v+) /* 按长度递增的次序，依次求得v0 到某个顶点

23、v的最短路径，如右代码 */ ,min = INFINITY; for (w=0; wG.numVertexes; w+) /* 寻找当前离v0最近的顶点 */ if (!finalw ,时间复杂度：O(n2),思考：如果求v0到特定顶点的最短路径，算法会简化吗？如果求所有顶点之间的最短路径呢？,弗洛伊德(Floyd)算法,用途：求任意两个顶点之间的最短路径 思路：邻接矩阵迭代,08/07/2020,38,1,5,2,V0,V1,V2,V0,V1,V2,D-1,V0,V1,V2,V0,V1,V2,V0,V1,V2,V0,V1,V2,D0,因为D-112D-110+D-102,所以D-112=D

24、-110+D-102,V0,V1,V2,V0,V1,V2,P-1,V0,V1,V2,V0,V1,V2,P0,所以P-112=P-110,Dvw=L表示从顶点v到顶点w的最短路径长度是L； Pvw=k表示从相应的从顶点v到顶点w的最短路径从v出发要先经过顶点k。,弗洛伊德 (Floyd)算法代码实现,08/07/2020,39,/* Floyd算法，各参数和D，P数组如前定义 */ void ShortestPath_Floyd(MGraph G, PathMatrix ,时间复杂度：O(n3),思考：刚才两个算法举例都是无向图，那么对有向图而言，两个算法是否依然有效？,内容提要,图的定义 图的

25、存储结构 图的遍历 最小生成树 最短路径 拓扑排序 关键路径,08/07/2020,40,拓扑排序,在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，我们称为AOV网(Activity On Vertex Network)。 设G=(V,E)是一个具有n个顶点的有向图，V中的顶点序列v1,v2,，vn，满足若从顶点vi到vj有一条路径，则在顶点序列中顶点vi必在顶点vj之前。则称这样的顶点序列为一个拓扑序列。拓扑排序就是对一个有向图构造拓扑序列的过程。,08/07/2020,41,导演确定,剧本完善,电影制作启动,投资确定,电影制作完成上映,

26、剧本初步完成,演职人员确定,V0,V2,V5,V6,人员到位进驻场地,V8,前期准备,场地确定,场景拍摄1,场景拍摄2,场景拍摄3,场景拍摄4,后期制作1,后期制作2,商业宣传,V7,V3,V1,V4,V15,V13,V9,V10,V11,V12,V14,V16,拓扑排序算法,基本思路：(1)从AOV网中选择一个入度为0的顶点输出;(2)删去此顶点，并删除以此顶点为尾的弧。继续重复这两个步骤，直到输出全部顶点或者AOV网中不存在入度为0的顶点为止。,08/07/2020,42,0,下标,0,V0,data,firstarc,indegree,11,0,V1,8,2,V2,9,0,V3,13,1

27、,2,3,2,4,V4,7,3,V5,12,1,V6,5,2,V7,5,6,7,2,8,V8,7,2,V9,11,1,V10,13,2,V11,9,10,11,1,V12,9,2,V13,12,13,adjvex,nextarc,5,4,4,2,6,5,2,8,10,V0,V1,V2,V3,V6,V5,V4,V7,V8,V9,V10,V13,V12,V11,1,4,3,2,1,0,V0,V1,V3,1,1,1,0,V2,2,0,1,V6,1,v3,v1,v2,v6,v0,0,0,1,V4,V5,vertices,拓扑排序算法代码实现,08/07/2020,43,Status Topologic

28、alSort(ALGraph G) / 有向图G采用邻接表存储结构，顶点表和边表结构如前页所示，G.vernum表示顶点数 / 若G无回路，则输出G 的顶点的一个拓扑序列并返回OK，否则ERROR FindInDegree(G, indegree); / 对各顶点求入度indegree0.G.vernum-1 InitStack(S); / 建零入度顶点栈S for (i=0; inextarc) k = p-adjvex; if (!(-indegreek) Push(S, k); / 若入度减为0，则入栈 / for / while if (countG.vexnum) return ER

29、ROR; / 该有向图有回路 else return OK; ,时间复杂度：O(n+e),内容提要,图的定义 图的存储结构 图的遍历 最小生成树 最短路径 拓扑排序 关键路径,08/07/2020,44,关键路径,与AOV网对应的是AOE网(Activity On Edge)即边表示活动的网。AOE网是一个带权的有向无环图，其中，顶点表示事件(Event)，弧表示活动，权表示活动持续的时间。通常，AOE网可用来估算工程的完成时间。 AOE网通常研究的问题是：（1）完成整个工程至少需要多少时间？（2）哪些活动是影响工程进度的关键？路径长度最长的路经叫关键路径（Critical Path）。,08/07/2020,45,造外壳,开始,集中,其他零部件,造发动机,造轮子,造底盘,组装,完成,外壳完成,开始,其他零部件完成,发动机完成