严蔚敏版数据结构(C语言版)PPT-第七章

《严蔚敏版数据结构(C语言版)PPT-第七章》由会员分享，可在线阅读，更多相关《严蔚敏版数据结构(C语言版)PPT-第七章（78页珍藏版）》请在装配图网上搜索。

1、1数数 据据 结结 构构7.1 图的定义与相关术语图的定义与相关术语7.2 图的存储结构图的存储结构7.4 最小生成树最小生成树第第 7 章章 图图7.3 图的遍历图的遍历7.5 最最短路径短路径7.5.2 关键路径关键路径7.5.1 拓扑排序拓扑排序2数数 据据 结结 构构7.1 图的定义与相关术语图的定义与相关术语第第 7 章章 图图图的结构定义图的结构定义:图是由图是由顶点集顶点集 V 和和弧集弧集 R构成的数据结构。构成的数据结构。Graph=(V,E)其中其中:V=|vDataObject R=E E=|P(v,w)且且(v,wV)表示从表示从 v 到到 w 的一条弧，并称的一条弧，

2、并称 v 为弧尾，为弧尾，w 为弧头。为弧头。谓词谓词 P(v,w)定义了弧定义了弧 的意义或信息的意义或信息,表示从表示从v到到w的一条单向通道。的一条单向通道。3数数 据据 结结 构构7.1 图的定义与相关术语图的定义与相关术语第第 7 章章 图图有向图有向图：由于由于“弧弧”是有方向的，因此称是有方向的，因此称 由由顶点集顶点集和和弧集弧集构成的图为有向图。构成的图为有向图。例如例如:ABCDE其中其中V1=A,B,C,D,EE1=,4数数 据据 结结 构构7.1 图的定义与相关术语图的定义与相关术语第第 7 章章 图图无向图无向图：由：由顶点集顶点集和和边集边集构成的图称作无向图。构成

3、的图称作无向图。例如例如:其中其中V2=A,B,C,D,E,FE2=(A,B),(A,E),(B,E),(C,D),(D,F),(B,F),(C,F)若若 VR 必有必有 VR,则以则以(v,w)代代替这两个有序对替这两个有序对,称称v 和和 w之间存在一条之间存在一条边边。ABCDEF5数数 据据 结结 构构7.1 图的定义与相关术语图的定义与相关术语第第 7 章章 图图名词和基本术语名词和基本术语假设图中有假设图中有 n 个顶点个顶点,e 条边条边,则则含含 e=n(n-1)/2 条条边边的无向图称作的无向图称作完全图完全图；含含 e=n(n-1)条条弧弧的有向图称作的有向图称作有向完全图

4、有向完全图；若边或弧的个数若边或弧的个数 enlogn，则称作，则称作稀疏图稀疏图，否则称作否则称作稠密图稠密图。6数数 据据 结结 构构7.1 图的定义与相关术语图的定义与相关术语第第 7 章章 图图名词和基本术语名词和基本术语若若无向图无向图顶点顶点v 和和w 之间存在一条边之间存在一条边(v,w),则则称顶点称顶点v 和和w 互为互为邻接点邻接点,称边称边(v,w)依附于依附于顶顶点点v 和和w 或边或边(v,w)与顶点与顶点v 和和w相关联相关联。与顶点与顶点v 关联的边的数目关联的边的数目定义为定义为v的的度（度（ID）。例如例如:ABCDEFID(B)=ID(A)=327数数 据据

5、 结结 构构7.1 图的定义与相关术语图的定义与相关术语第第 7 章章 图图名词和基本术语名词和基本术语对于对于有向图有向图，若顶点，若顶点v 和和w 之间之间存在一条弧存在一条弧则称则称顶点顶点v邻接到顶点邻接到顶点w,顶点顶点w邻接自邻接自顶点顶点v,称弧称弧与顶点与顶点v 和和w 相关联相关联。以以v为为尾尾的弧的数目定义为的弧的数目定义为v的的出度（出度（OD）。例如例如:OD(B)=ID(B)=以以v为为头头的弧的数目定义为的弧的数目定义为v的的入度（入度（ID）。出度出度+入度入度=该顶点的度（该顶点的度（TD）ABCDETD(B)=1238数数 据据 结结 构构7.1 图的定义与

6、相关术语图的定义与相关术语第第 7 章章 图图名词和基本术语名词和基本术语设图设图G=(V,VR)中的中的 u=vi,0,vi,1,vi,m=w顶点顶点序列中序列中,有有(vi,j-1,vi,j)VR 1jm,则称从顶点则称从顶点u到到顶点顶点w之间存在一条之间存在一条路径路径。路径上边的数目称作路径上边的数目称作路路径长度径长度，有向图的有向图的路径也是路径也是有向的。有向的。例如例如:路径路径A,E,C,D,B,C,D路径长度为路径长度为6ABCDE9数数 据据 结结 构构7.1 图的定义与相关术语图的定义与相关术语第第 7 章章 图图名词和基本术语名词和基本术语回路回路:首尾顶点相同的路

7、径。首尾顶点相同的路径。简单路径简单路径:顶点不重复的路径。顶点不重复的路径。A,E,C,D简单回路简单回路:中间顶点不重中间顶点不重的回路的回路ABCDEB,C,D,B A,E,C,D,B,C,D,AA,E,C,D,A10数数 据据 结结 构构7.1 图的定义与相关术语图的定义与相关术语第第 7 章章 图图名词和基本术语名词和基本术语例如例如:设图设图G=(V,VR)和图和图 G=(V,VR),且且 VV,VRVR,则称则称 G 为为 G 的的子图子图。ABCDEBCDAEDA11数数 据据 结结 构构7.1 图的定义与相关术语图的定义与相关术语第第 7 章章 图图名词和基本术语名词和基本术

8、语若若无向图无向图G中中任意两个顶点之间都任意两个顶点之间都有路径相通有路径相通,则称此图为则称此图为连通图连通图。若无向图为非连通图，则图中各个若无向图为非连通图，则图中各个极大连通子图极大连通子图称作此图的称作此图的连通分量连通分量。ABCDEFABCDEFBAECFD12数数 据据 结结 构构7.1 图的定义与相关术语图的定义与相关术语第第 7 章章 图图名词和基本术语名词和基本术语对对有向图有向图,若任意两个顶点之间都存在一若任意两个顶点之间都存在一条有向路径，则称此有向图为条有向路径，则称此有向图为强连通图强连通图。否则否则,其各强连通子图称作它的其各强连通子图称作它的强连通分量强连

9、通分量。ABCDEABCDEBCDAE13数数 据据 结结 构构7.1 图的定义与相关术语图的定义与相关术语第第 7 章章 图图名词和基本术语名词和基本术语假设一个假设一个连通图连通图有有 n 个顶点和个顶点和 e 条边条边,其中其中 n-1 条边和条边和 n 个顶点构成一个个顶点构成一个极小连通子图极小连通子图,称该极小连通子图为此连通图的称该极小连通子图为此连通图的生成树生成树。ABCDEFABCDFE14数数 据据 结结 构构7.1 图的定义与相关术语图的定义与相关术语第第 7 章章 图图名词和基本术语名词和基本术语对对非连通图非连通图，则称由各个连通分量的生成树，则称由各个连通分量的生

10、成树的集合为此非连通图的的集合为此非连通图的生成森林生成森林。ABCDEFABCDEF15有向图有向图或或无向图无向图中的弧或边中的弧或边带权带权后的图分别称作后的图分别称作有向网有向网或或无向网无向网。数数 据据 结结 构构7.1 图的定义与相关术语图的定义与相关术语第第 7 章章 图图ABCDE159117322116数数 据据 结结 构构7.2图的存储结构图的存储结构第第 7 章章 图图图的邻接矩阵表示法图的邻接矩阵表示法图的邻接表表示法图的邻接表表示法有向图的十字链表表示法有向图的十字链表表示法无向图的邻接多重表表示法无向图的邻接多重表表示法17数数 据据 结结 构构7.2图的存储结构

11、图的存储结构第第 7 章章 图图图的邻接矩阵表示法图的邻接矩阵表示法（数组表示法）（数组表示法）一维数组：一维数组：二维数组：二维数组：用于存储顶点信息。用于存储顶点信息。用于存储图中顶点之间用于存储图中顶点之间关联关系关联关系邻接矩阵邻接矩阵Ai,j=1若若或（或（vi,vj）VR0 反之反之ABCDEF0 1 0 0 1 01 0 0 0 1 10 0 0 1 0 10 0 1 0 0 11 1 0 0 0 00 1 1 1 0 0ABCDEFA B C D E F无向图无向图对对称称矩矩阵阵18数数 据据 结结 构构7.2图的存储结构图的存储结构第第 7 章章 图图图的邻接矩阵表示法图的

12、邻接矩阵表示法（数组表示法）（数组表示法）一维数组：一维数组：二维数组：二维数组：用于存储顶点信息。用于存储顶点信息。用于存储图中顶点之间用于存储图中顶点之间关联关系关联关系邻接矩阵邻接矩阵Ai,j=1若若或（或（vi,vj）VR0 反之反之0 1 0 0 10 0 1 0 00 0 0 1 01 1 0 0 00 0 1 0 0ABCDEA B C D EABCDE有向图有向图非非对对称称矩矩阵阵19数数 据据 结结 构构7.2图的存储结构图的存储结构第第 7 章章 图图图的邻接矩阵表示法图的邻接矩阵表示法（数组表示法）（数组表示法）一维数组：一维数组：二维数组：二维数组：用于存储顶点信息。

13、用于存储顶点信息。用于存储图中顶点之间用于存储图中顶点之间关联关系关联关系邻接矩阵邻接矩阵Ai,j=1若若或（或（vi,vj）VR0 反之反之15 9 3 211 7 21 ABCDEA B C D EABCDE1591173221wij有向网有向网非非对对称称矩矩阵阵20数数 据据 结结 构构7.2图的存储结构图的存储结构第第 7 章章 图图图的邻接矩阵表示法图的邻接矩阵表示法（数组表示法）（数组表示法）特点：特点：.存储空间存储空间.便于运算便于运算无向图：无向图：n(n-1)/2有向图（网）：有向图（网）：n2无向图：无向图：TD（v vi i）=A i,j i,j j=1j=1n n有

14、向图（网）：有向图（网）：OD（v vi i）=A i,j i,j j=1j=1n nID（v vi i）=A j,i j,i j=1j=1n n21数数 据据 结结 构构7.2图的存储结构图的存储结构第第 7 章章 图图图的邻接表表示法图的邻接表表示法（链式存储法）（链式存储法）.表头结点表头结点.表结点表结点对图中每个顶点建立一个单链表，第对图中每个顶点建立一个单链表，第i i个个单链表中的结点表示依附于顶点单链表中的结点表示依附于顶点vi i的边。的边。datafirst 图图adjvex nextarc网网adjvexnextarcinfo22数数 据据 结结 构构7.2图的存储结构图

15、的存储结构第第 7 章章 图图图的邻接表表示法图的邻接表表示法（链式存储法）（链式存储法）ABCDEF12345625 156 46 36 12 234 ABCDEF无向图无向图23数数 据据 结结 构构7.2图的存储结构图的存储结构第第 7 章章 图图图的邻接表表示法图的邻接表表示法（链式存储法）（链式存储法）ABCDE1234525 3 4 12 3 ABCDE有向图有向图24数数 据据 结结 构构7.2图的存储结构图的存储结构第第 7 章章 图图图的邻接表表示法图的邻接表表示法（链式存储法）（链式存储法）ABCDE12345ABCDE1591173221有向网有向网2 155 9 3 3

16、 4 2 1 112 7 3 2125数数 据据 结结 构构7.2图的存储结构图的存储结构第第 7 章章 图图图的邻接表表示法图的邻接表表示法（链式存储法）（链式存储法）特点：特点：.无向图存储空间：无向图存储空间：.n+2e无向图：无向图：TD（v vi i）=第第i i个单链表上结点的个数个单链表上结点的个数有向图（网）：有向图（网）：OD（v vi i）=第第i i个单链表上结点的个数个单链表上结点的个数ID（v vi i）扫描整个邻接表）扫描整个邻接表逆邻接表逆邻接表26数数 据据 结结 构构7.2图的存储结构图的存储结构第第 7 章章 图图图的邻接表表示法图的邻接表表示法（链式存储法

17、）（链式存储法）逆邻接表逆邻接表ABCDE有向图有向图ABCDE123454 4 5 3 1 1227数数 据据 结结 构构7.2图的存储结构图的存储结构第第 7 章章 图图有向图的十字链表表示法有向图的十字链表表示法（链式存储法）（链式存储法）顶点和弧分别各用一种存储结构的结点表示。顶点和弧分别各用一种存储结构的结点表示。弧头弧头相同的弧被链在同一链表上相同的弧被链在同一链表上，弧尾相同的弧也被链弧尾相同的弧也被链在同一链表上在同一链表上，链表的，链表的头结点头结点就是就是顶点顶点结点。结点。弧的结点结构弧的结点结构顶点的结点结构顶点的结点结构tailvex headvex hlink tl

18、inkdata firstin firstout28数数 据据 结结 构构7.2图的存储结构图的存储结构第第 7 章章 图图有向图的十字链表表示法有向图的十字链表表示法ABCDE有向图有向图12345ABCDE1 21 52 33 44 14 25 329数数 据据 结结 构构7.2图的存储结构图的存储结构第第 7 章章 图图无向图的邻接多重表表示无向图的邻接多重表表示法法顶点和边分别各用一种存储结构的结点表示。顶点和边分别各用一种存储结构的结点表示。依附于相同依附于相同顶点的边被链在同一链表上顶点的边被链在同一链表上，每条边依附于两个顶点，每条边依附于两个顶点，所所以每个边结点同时被链接在两

19、个链表中以每个边结点同时被链接在两个链表中，链表的头结点就链表的头结点就是顶点结点是顶点结点。同时还在边结点中增加了一个访问标志位。同时还在边结点中增加了一个访问标志位。边的结点结构边的结点结构顶点的结点结构顶点的结点结构mark ivex ilinkjlinkjvexdatafirstedge30数数 据据 结结 构构7.2图的存储结构图的存储结构第第 7 章章 图图无向图的邻接多重表表示无向图的邻接多重表表示法法无向图无向图ABCDEABCDE1234512143234523531无向图无向图ABCDE0 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 00 1 1 0

20、0ABCDEA B C D E32数数 据据 结结 构构7.3 图的遍历图的遍历第第 7 章章 图图从图中从图中某个顶点某个顶点出发遍历图，访遍图中出发遍历图，访遍图中其余顶其余顶点点，并且使图中的，并且使图中的每个顶点仅被访问一次每个顶点仅被访问一次的过程。的过程。深度优先搜索深度优先搜索广度优先搜索广度优先搜索33数数 据据 结结 构构7.3 图的遍历图的遍历第第 7 章章 图图深度优先搜索深度优先搜索 基本思想：基本思想：.从图中某个顶点从图中某个顶点v v0 0出发，出发，首先访问首先访问v v0 0 ;类似于树的先根次序遍历类似于树的先根次序遍历.找出刚访问过的顶点的找出刚访问过的顶

21、点的第一个未被第一个未被访问的邻接点，访问的邻接点，然后访问该顶点。以该顶点为新顶点，重复此步骤，然后访问该顶点。以该顶点为新顶点，重复此步骤，直到刚访问过的顶点直到刚访问过的顶点没有未被访问没有未被访问的邻接点为止；的邻接点为止；.返回前一个返回前一个访问过的且访问过的且仍有未被访问仍有未被访问的邻接点的顶的邻接点的顶 点，找出该顶点的点，找出该顶点的下一个未被访问下一个未被访问的邻接点，访问的邻接点，访问 该顶点。然后执行步骤该顶点。然后执行步骤。34ABCDEFGHI数数 据据 结结 构构7.3 图的遍历图的遍历第第 7 章章 图图深度优先搜索深度优先搜索例如：例如：ABCABCFEFE

22、GGDDHHII回到回到A结束！结束！深深度度优优先先搜搜索索树树每个顶点设置一个标志用于检查是否被访问过，每个顶点设置一个标志用于检查是否被访问过，即设置数组即设置数组visitedn，visitedi=0 未访问未访问1 已访问已访问35数数 据据 结结 构构7.3 图的遍历图的遍历第第 7 章章 图图深度优先搜索深度优先搜索算法思想：算法思想：递归递归.访问出发点访问出发点v v0 0 ;.依次以依次以v v0 0的未被访问的邻接点为出发点，的未被访问的邻接点为出发点，深度优先搜索图深度优先搜索图，直至图中所有与，直至图中所有与v v0 0有有 路径相通的顶点都被访问。路径相通的顶点都被

23、访问。对于对于非连通图非连通图，则图中一定还有顶点未被访，则图中一定还有顶点未被访问，要从图中问，要从图中另选一个未被访问的顶点作为另选一个未被访问的顶点作为起始点起始点，重复上述深度优先搜索过程。，重复上述深度优先搜索过程。36数数 据据 结结 构构深度优先搜索深度优先搜索深度优先遍历图深度优先遍历图g的算法描述的算法描述void DFS(int*visited,int v)/*visited数组存储顶点的遍历情况数组存储顶点的遍历情况*/GraphNode*p;visitedv=1;/*已访问的顶点已访问的顶点,visitedv置为置为1 */printf(%d-,v);p=Graphv.

24、next;/*p指向第指向第v个顶点的第一个邻接点个顶点的第一个邻接点 */while(p!=NULL)if(visitedp-data=0)DFS(visited,p-data);/*递归调用递归调用*/p=p-next;无向图无向图ABCDE37数数 据据 结结 构构7.3 图的遍历图的遍历第第 7 章章 图图深度优先搜索深度优先搜索非递归形式的非递归形式的DepthFirstSearch.首先将首先将v0入栈；入栈；.只要栈不空，则重复下述处理：只要栈不空，则重复下述处理：a.栈顶顶点出栈，如果未访问，则访问并置访问标志；栈顶顶点出栈，如果未访问，则访问并置访问标志；b.然后将然后将v0

25、所有未访问的邻接点入栈。所有未访问的邻接点入栈。ABCDEFGHIA000000000IHGFEDCBAvisitednA1EDBB1ECC1FF1E1GG1HDD1H1II138数数 据据 结结 构构7.3 图的遍历图的遍历第第 7 章章 图图广度优先搜索广度优先搜索 基本思想：基本思想：.从图中某个顶点从图中某个顶点v v0 0出发，出发，首先访问首先访问v v0 0 ;.依次访问依次访问v v0 0各个未被访问的邻接点各个未被访问的邻接点；.分别从这些邻接点出发，依次访问它们的各个分别从这些邻接点出发，依次访问它们的各个未未 被访问的邻接点被访问的邻接点。访问时应保证：如果。访问时应保证

26、：如果v vi i和和v vk k为为 当前端结点，且当前端结点，且v vi i在在v vk k之前被访问，则之前被访问，则v vi i的所有未的所有未 被访问的邻接点应在被访问的邻接点应在v vk k所有未被访问的邻接点之所有未被访问的邻接点之 前访问。重复前访问。重复，直到所有端结点均没有未被，直到所有端结点均没有未被 访问的邻接点为止。访问的邻接点为止。类似于树的层次遍历类似于树的层次遍历39数数 据据 结结 构构7.3 图的遍历图的遍历第第 7 章章 图图例如：例如：ABCDEFGHIABABDECGFH I广广度度优优先先搜搜索索树树每个顶点设置一个标志用于检查是否访问过，每个顶点设

27、置一个标志用于检查是否访问过，即设置数组即设置数组visitedn，visitedi=0 未访问未访问1 已访问已访问广度优先搜索广度优先搜索EDCFGHI需要辅助需要辅助队列队列Q，以便实现访问时应保证的一点！，以便实现访问时应保证的一点！40数数 据据 结结 构构广度优先搜索广度优先搜索广度优先遍历图广度优先遍历图g的算法描述的算法描述void BFS(int*visited,int v,int*Queue)GraphNode*p;AddQuene(Queue,v);/*初始顶点入队初始顶点入队 */visitedv=1;/*已访问的顶点已访问的顶点 */printf(%d-,v);/*显

28、示显示*/while(front!=rear)/*队列不为空队列不为空*/v=Delquene(Queue);/*取出队头元素取出队头元素 */p=Graphv.next;/*邻接顶点邻接顶点*/while(p!=NULL)/*有邻接顶点有邻接顶点 */if(visitedp-data=0)/*没有遍历过没有遍历过 */AddQuene(Queue,p-data);/*v的邻接顶点入队的邻接顶点入队 */visitedp-data=1;printf(%d-,p-data);p=p-next;/*访问下一个邻接顶点访问下一个邻接顶点 */41数数 据据 结结 构构7.3 图的遍历图的遍历第第 7

29、 章章 图图算法思想：算法思想：.访问出发点访问出发点v v0 0 并置访问标志，然后将并置访问标志，然后将v v0 0入队入队;广度优先搜索广度优先搜索.只要队不空，则重复下述处理：只要队不空，则重复下述处理：a.队头结点队头结点v出队；出队；b.对对v的所有邻接点的所有邻接点w，如果，如果w未被访问，则未被访问，则 访问访问w并置访问标志，然后并置访问标志，然后w入队。入队。ABCDEFGHI000000000IHGFEDCBAvisitednA1ABDE111BDEC1CG1GF1FH1HI1I42数数 据据 结结 构构7.4 最小生成树最小生成树第第 7 章章 图图图的连通性问题图的连

30、通性问题有向无环图的应用有向无环图的应用最短路径问题最短路径问题43数数 据据 结结 构构7.4 最小生成树最小生成树第第 7 章章 图图可以利用图的遍历来判断一个图是否连通，如果可以利用图的遍历来判断一个图是否连通，如果在遍历的过程中，在遍历的过程中，不止一次不止一次调用搜索过程，则说调用搜索过程，则说明该图就是一个明该图就是一个非连通图非连通图，并且，并且几次调用几次调用搜索过搜索过程，表明该图就有程，表明该图就有几个几个连通分量。连通分量。1.图的连通性问题图的连通性问题无向图的连通分量无向图的连通分量AJCFEGBIDHABDCIEFGHJ44数数 据据 结结 构构7.4 最小生成树最

31、小生成树第第 7 章章 图图有条件的图的遍历过程。有条件的图的遍历过程。1.图的连通性问题图的连通性问题图中两个顶点之间的简单路径图中两个顶点之间的简单路径求从顶点求从顶点 B B 到顶点到顶点 K K 的一条简单路径。的一条简单路径。ABGCDEFHK例如：例如：从顶点从顶点B出发进行深度优先搜索遍历。出发进行深度优先搜索遍历。ABCDEKHABEK45数数 据据 结结 构构7.4 最小生成树最小生成树第第 7 章章 图图1.图的连通性问题图的连通性问题图的生成树与最小生成树图的生成树与最小生成树生成树：生成树：若图若图G是是连通图连通图,从图中某一顶点出发从图中某一顶点出发遍历图时，图中遍

32、历图时，图中所有的顶点所有的顶点加上遍历加上遍历时经过的时经过的边边所构成的子图称为所构成的子图称为生成树生成树。一个连通图的生成树一个连通图的生成树是指一个是指一个极小连通子图极小连通子图，含有图中的全部含有图中的全部n个顶点个顶点，但只有足以构成一，但只有足以构成一棵树的棵树的n-1条边条边。46数数 据据 结结 构构7.4 最小生成树最小生成树第第 7 章章 图图1.图的连通性问题图的连通性问题图的生成树与最小生成树图的生成树与最小生成树该问题等价于：该问题等价于：构造构造网网的一棵最小生成树，即：在的一棵最小生成树，即：在 e 条带权的边中选条带权的边中选取取 n-1 条边（不构成回路

33、），使条边（不构成回路），使“权值之和权值之和”为最小。为最小。假设要在假设要在 n 个城市之间建立通讯联络网，则连通个城市之间建立通讯联络网，则连通 n 个城市只需要修建个城市只需要修建 n-1条线路，条线路，如何在最节省经如何在最节省经费的前提下建立这个通讯网？费的前提下建立这个通讯网？47数数 据据 结结 构构7.4 最小生成树最小生成树第第 7 章章 图图1.图的连通性问题图的连通性问题图的生成树与最小生成树图的生成树与最小生成树.尽可能选取尽可能选取权值小权值小的边，但的边，但不不能能构成回路构成回路。.选取选取n-1条条恰当的恰当的边边以连接网的以连接网的n个顶点个顶点。算法一：克

34、鲁斯卡尔算法算法一：克鲁斯卡尔算法(Kruskal)算法二：普里姆算法算法二：普里姆算法(Prim)最小生成树的要解决的两个问题：最小生成树的要解决的两个问题：48数数 据据 结结 构构7.4 最小生成树最小生成树第第 7 章章 图图1.图的连通性问题图的连通性问题图的生成树与最小生成树图的生成树与最小生成树算法一：克鲁斯卡尔算法算法一：克鲁斯卡尔算法(Kruskal)考虑问题的出发点考虑问题的出发点:为使生成树为使生成树上边的权值之和达到最小上边的权值之和达到最小，则，则应使生成树中每一条边的权值尽可能地小。应使生成树中每一条边的权值尽可能地小。具体做法具体做法:先构造一个只含先构造一个只含

35、 n 个顶点的子图个顶点的子图 SG，然后然后从权值最小的边从权值最小的边开始，若它的添加开始，若它的添加不不使使SG 中中产生回路产生回路，则在，则在 SG 上加上这条边，如此重复，上加上这条边，如此重复，直至加上直至加上 n-1 条边为止。条边为止。加边法加边法49数数 据据 结结 构构7.4 最小生成树最小生成树第第 7 章章 图图1.图的连通性问题图的连通性问题图的生成树与最小生成树图的生成树与最小生成树算法一：克鲁斯卡尔算法算法一：克鲁斯卡尔算法(Kruskal)实例实例算法步骤如下算法步骤如下;（1）边的权值首先从小到大排序。）边的权值首先从小到大排序。（2）从所有的未遍历的边中取

36、出最小权值的边，）从所有的未遍历的边中取出最小权值的边，记录此遍历并检查是否形成回路。记录此遍历并检查是否形成回路。50数数 据据 结结 构构1.所有的边按权值从小到大排序所有的边按权值从小到大排序5(B,C)BAEFDC19183321111465616BAEFDC181165166(B,D)6(C,D)11(B,E)14(D,E)16(A,B)18(D,F)19(A,F)21(A,E)33(E,F)2.顶点集合状态顶点集合状态:(B,C)(B,D)(B,E)(A,B)(D,F)A B C D E F B,C B,C,D B,C,D,E B,C,D,E,A B,C,D,E,A,F3.最小生成

37、树边的集合：最小生成树边的集合：51数数 据据 结结 构构7.4 最小生成树最小生成树第第 7 章章 图图1.图的连通性问题图的连通性问题图的生成树与最小生成树图的生成树与最小生成树算法二：普里姆算法算法二：普里姆算法(Prim)基本思想基本思想:取图中任意一个顶点取图中任意一个顶点v作为生成树的根，之作为生成树的根，之后往生成树上添加新的顶点后往生成树上添加新的顶点w。在添加的顶点在添加的顶点w 和已经在生成树上的顶点和已经在生成树上的顶点v之间必定存在一条边，之间必定存在一条边，该边的权值在所有连通顶点该边的权值在所有连通顶点 v 和和 w 之间的边中之间的边中取值最小取值最小。之后继续往

38、生成树上添加顶点，直至。之后继续往生成树上添加顶点，直至生成树上含有生成树上含有 n 个顶点为止。个顶点为止。52数数 据据 结结 构构7.4 最小生成树最小生成树第第 7 章章 图图1.图的连通性问题图的连通性问题图的生成树与最小生成树图的生成树与最小生成树算法二：普里姆算法算法二：普里姆算法(Prim)一般情况下所添加的顶点应满足条件一般情况下所添加的顶点应满足条件:在生成树的构造过程中在生成树的构造过程中,图中图中 n 个顶点个顶点分属两个集合分属两个集合:已落在生成树上的顶点集已落在生成树上的顶点集 U 和和尚未落在生成树上的顶点集尚未落在生成树上的顶点集 V-U;则应在所有连通则应在

39、所有连通U中顶点和中顶点和V-U中顶点的边中中顶点的边中 选取权值最小的边选取权值最小的边。基本思想基本思想:加点法加点法53数数 据据 结结 构构7.4 最小生成树最小生成树第第 7 章章 图图1.图的连通性问题图的连通性问题图的生成树与最小生成树图的生成树与最小生成树算法二：普里姆算法算法二：普里姆算法(Prim)实例实例:abcdegf191827211271431658abcdegf54数数 据据 结结 构构7.4 最小生成树最小生成树第第 7 章章 图图1.图的连通性问题图的连通性问题图的生成树与最小生成树图的生成树与最小生成树算法二：普里姆算法算法二：普里姆算法(Prim)算法思想

40、算法思想设设N=(V,E)是连通网是连通网,TE是是N上最小生成树上最小生成树中中边边的的集合集合。初始。初始U=u0,(u0V),TE=，然后重复执行下述运算：然后重复执行下述运算：在所有在所有uU，vV-U的边的边(u,v)E中，找一中，找一条代价最小的边条代价最小的边(u0,v0)并入集合并入集合TE，同时，同时v0并入并入U，直到，直到U=V，则可生成一棵具有最小代，则可生成一棵具有最小代价的生成树价的生成树 T=(V,TE)。55数数 据据 结结 构构7.4 最小生成树最小生成树第第 7 章章 图图1.图的连通性问题图的连通性问题图的生成树与最小生成树图的生成树与最小生成树算法二：普

41、里姆算法算法二：普里姆算法(Prim)算法思想算法思想连通网用连通网用带权的邻接矩阵带权的邻接矩阵表示表示,并设置一个并设置一个辅助数组辅助数组closedge ，数组元素下标对应当前数组元素下标对应当前V-U集中的顶点集中的顶点序号，序号，元素值则记录该顶点和元素值则记录该顶点和 U集中相连接的代价集中相连接的代价最小最小(最近最近)边的顶点序号边的顶点序号adjvex和权值和权值lowcost。即对即对vV-U的每个顶点，的每个顶点，closedgev记录所有记录所有与与v邻接的、从邻接的、从U到到V-U的那组边中的最小边的信息。的那组边中的最小边的信息。56数数 据据 结结 构构7.4

42、最小生成树最小生成树第第 7 章章 图图1.图的连通性问题图的连通性问题图的生成树与最小生成树图的生成树与最小生成树算法二：普里姆算法算法二：普里姆算法(Prim)算法思想算法思想辅助数组：辅助数组：mincost(u,v)|uU,vV-Uclosedgev.lowcost=0 vUclosedgev.adjvex 存放存放U中与中与v最近的顶点序号。最近的顶点序号。57数数 据据 结结 构构7.4 最小生成树最小生成树第第 7 章章 图图1.图的连通性问题图的连通性问题图的生成树与最小生成树图的生成树与最小生成树算法二：普里姆算法算法二：普里姆算法(Prim)算法思想演示算法思想演示abcd

43、egf191827211271431658abcdegf 19 14 1819 5 7 12 5 3 7 3 8 21 14 12 8 16 21 27 18 16 27 lowcostadjvex7g6f5e4d3c2b1aclosedgev01a191a141a18 05e125e85e16 04d 74d34d21 03c5 0 0 0算法思想演示算法思想演示58数数 据据 结结 构构.图的生成树不唯一，从不同的顶点出发进行遍图的生成树不唯一，从不同的顶点出发进行遍历，可以得到不同的生成树历，可以得到不同的生成树;.即是从相同的顶点出发，在选择最小边时，可能有即是从相同的顶点出发，在选择

44、最小边时，可能有多条同样的边可选，此时任选其一。多条同样的边可选，此时任选其一。7.4 最小生成树最小生成树第第 7 章章 图图1.图的连通性问题图的连通性问题图的生成树与最小生成树图的生成树与最小生成树59数数 据据 结结 构构7.4 最小生成树最小生成树第第 7 章章 图图1.图的连通性问题图的连通性问题图的生成树与最小生成树图的生成树与最小生成树O(nO(n2 2)O(elogeO(eloge)稠密图稠密图稀疏图稀疏图比较两种算法比较两种算法时间复杂度时间复杂度普里姆算法普里姆算法算法名算法名适应范围适应范围克鲁斯卡尔算法克鲁斯卡尔算法60数数 据据 结结 构构7.5 有向无环图及其应用

45、有向无环图及其应用第第 7 章章 图图2.有向无环图的应用有向无环图的应用带权图的最短路径带权图的最短路径从某顶点从某顶点(源点源点)出发到另一顶点出发到另一顶点(目的点目的点)的路径中的路径中,有一条有一条各边各边(或弧或弧)权值之和最小的路径权值之和最小的路径称为称为最短路径最短路径。.从单源点到其余各点的最短路径从单源点到其余各点的最短路径 迪杰斯特拉算法迪杰斯特拉算法(Dijkstra).每一对顶点之间的最短路径每一对顶点之间的最短路径 弗洛伊德算法弗洛伊德算法(floyd)61数数 据据 结结 构构第第 7 章章 图图2.有向无环图的应用有向无环图的应用带权图的最短路径带权图的最短路

46、径.从单源点到其余各点的最短路径。从单源点到其余各点的最短路径。迪杰斯特拉算法迪杰斯特拉算法(Dijkstra)基本思想基本思想:依最短路径的长度递增的次序求得各条路径。依最短路径的长度递增的次序求得各条路径。源点源点V0vivj其中其中,从源点从源点v0到顶点到顶点vi的的最短路径是最短路径是v0到各点最短到各点最短路径集合中长度最短者路径集合中长度最短者。7.5 有向无环图及其应用有向无环图及其应用62数数 据据 结结 构构第第 7 章章 图图2.有向无环图的应用有向无环图的应用 迪杰斯特拉算法迪杰斯特拉算法(Dijkstra)v0v5v1v2v3v41003060101055020 最短

47、路径最短路径 长度长度（v0,v2）10（v0,v4）30（v0,v4,v3）50（v0,v4,v3,v5)60 v0v1 7.5 有向无环图及其应用有向无环图及其应用63数数 据据 结结 构构第第 7 章章 图图2.有向无环图的应用有向无环图的应用 迪杰斯特拉算法迪杰斯特拉算法(Dijkstra)路径长度最短的最短路径的特点：路径长度最短的最短路径的特点：在这条路径上，必定只含一条弧在这条路径上，必定只含一条弧,并且这条弧的权并且这条弧的权值最小。值最小。(设为设为v0 vi)下一条路径长度次短的最短路径的特点：下一条路径长度次短的最短路径的特点：它只可能有两种情况：它只可能有两种情况：或者

48、是直接从源点到该点或者是直接从源点到该点vj(只含一条弧只含一条弧);或者是从源点经过顶点或者是从源点经过顶点vi,再到达再到达vj(由由两条弧组成两条弧组成)。7.5 有向无环图及其应用有向无环图及其应用64其余最短路径的特点：其余最短路径的特点：再下一条路径长度次短的最短路径特点再下一条路径长度次短的最短路径特点:它可能有两种情况：它可能有两种情况：或者是直接从源点到该点或者是直接从源点到该点(只含一条弧只含一条弧)；或者是从源点经过顶点或者是从源点经过顶点vi、vj再再到达该顶点到达该顶点(由多条弧组成由多条弧组成)。它或者是直接从源点到该点它或者是直接从源点到该点(只含一条弧只含一条弧

49、)；或者是或者是 从源点经过已求得最短路径的顶点，再到达该顶点。从源点经过已求得最短路径的顶点，再到达该顶点。数数 据据 结结 构构第第 7 章章 图图2.有向无环图的应用有向无环图的应用 迪杰斯特拉算法迪杰斯特拉算法(Dijkstra)7.5 有向无环图及其应用有向无环图及其应用65数数 据据 结结 构构第第 7 章章 图图2.有向无环图的应用有向无环图的应用 迪杰斯特拉算法迪杰斯特拉算法实现思想实现思想一、存储结构一、存储结构1.带权邻接矩阵用带权邻接矩阵用g.arcs 表示表示;用用g.arcsij.adj表示弧表示弧上的上的权权。2.顶点分为两组：顶点分为两组：S，V-S S中存放中存

50、放已求得最短路径的终点的集合已求得最短路径的终点的集合。3.辅助一维数组辅助一维数组dist 若若viS,disti 表示源点到表示源点到vi的最短路径长度的最短路径长度 若若viV-S,disti表示源点到表示源点到vi的只包括的只包括S中的中的 顶点为中间顶点的最短路径。顶点为中间顶点的最短路径。初始：初始：S=v0 ,v0为源点为源点 disti=g.arcs0i.adj;(viV-S)7.5 有向无环图及其应用有向无环图及其应用66数数 据据 结结 构构第第 7 章章 图图2.有向无环图的应用有向无环图的应用 迪杰斯特拉算法迪杰斯特拉算法实现思想实现思想二、最短路径二、最短路径1、第一

51、条最短路径、第一条最短路径 distk=mindisti|viV-S 最短路径（最短路径（v0，vk），），S=S vk2、修改修改V-S中顶点的中顶点的dist值值 i V-S disti=mindisti，distk+g.arcski.adj3、下一条最短路径下一条最短路径 distj=min disti|viV-S4、vj并入集合并入集合S，重复，重复2，3，（，（n-1次）次）直到直到 v0出发可以到达的所有顶点都包含在出发可以到达的所有顶点都包含在S中中。7.5 有向无环图及其应用有向无环图及其应用67数数 据据 结结 构构第第 7 章章 图图2.有向无环图的应用有向无环图的应用 迪

52、杰斯特拉算法迪杰斯特拉算法实例实例7.5 有向无环图及其应用有向无环图及其应用68v5v2v41003060101055020v3v1v0终点终点 dist集合集合SV1V2V3V4V512345/0,2,4,3,5,160(V0,V4,V3,V5)/0,2,4,3,590(V0,V4,V5)/50(V0,V4,V3)/0,2,4,3100(V0,V5)30(V0,V4)60(V0,V2,V3)/0,2,4100(V0,V5)30(V0,V4)10(V0,V2)最短路径最短路径 长度长度 （v0,v2）1000,2v5v2v4301020v3v1v010（v0,v4）30（v0,v4,v3）5

53、0（v0,v4,v3,v5)60v0v1 无无69数数 据据 结结 构构7.5.1 拓扑排序拓扑排序第第 7 章章 图图2.有向无环图的应用有向无环图的应用无环的有向图称为有向无环图无环的有向图称为有向无环图,简称简称 DAG图图(Directed Acyclic Graph),它可以表示一个它可以表示一个工程或系统的流程图。工程或系统的流程图。一项大工程可以分为若干个称为活动的一项大工程可以分为若干个称为活动的子工程子工程,用用顶点顶点表示表示;某些子工程必须在另一些子工程完某些子工程必须在另一些子工程完成之后才能开始成之后才能开始,用用弧表示它们之间的前趋后继弧表示它们之间的前趋后继关系关

54、系;这样构成的有向图显然是无环的。如何使这样构成的有向图显然是无环的。如何使工程顺利进行工程顺利进行?完成总工程需要的最短时间完成总工程需要的最短时间?就就归结为归结为拓扑排序拓扑排序和和关键路径关键路径问题。问题。70数数 据据 结结 构构7.5.1 拓扑排序拓扑排序第第 7 章章 图图2.有向无环图的应用有向无环图的应用拓扑排序拓扑排序假设以有向图表示一个工程的施工图或程序的假设以有向图表示一个工程的施工图或程序的数据流图数据流图,每个每个顶点代表一个活动顶点代表一个活动,弧弧表示活动表示活动 i i 必须先于活动必须先于活动 j j 进行进行,称为称为AOV-网网(Activity On

55、 Vertex),图中不允许出现回路图中不允许出现回路。检查有向图中是否存在回路的方法检查有向图中是否存在回路的方法之一，是对有向图进行之一，是对有向图进行拓扑排序拓扑排序。还可以使用还可以使用DFS71数数 据据 结结 构构7.5.1 拓扑排序拓扑排序第第 7 章章 图图2.有向无环图的应用有向无环图的应用拓扑排序拓扑排序何谓何谓“拓扑排序拓扑排序”？对有向图进行如下操作：对有向图进行如下操作：按照按照有向图给出的次序关系有向图给出的次序关系,将图中将图中顶点排成一个顶点排成一个线性序列线性序列,对于有向图中没有限定次序关系的顶点对于有向图中没有限定次序关系的顶点,则可以人为加上任意的次序关

56、系则可以人为加上任意的次序关系,由此由此所得顶点的所得顶点的线性序列称之为拓扑有序序列线性序列称之为拓扑有序序列。显然对于有回路。显然对于有回路的有向图得不到拓扑有序序列。的有向图得不到拓扑有序序列。72数数 据据 结结 构构7.5.1 拓扑排序拓扑排序第第 7 章章 图图2.有向无环图的应用有向无环图的应用拓扑排序拓扑排序例如：例如：可求得可求得拓扑有序序列：拓扑有序序列：A B C D 或或 A C B DBDAC存在回路，活动互存在回路，活动互为前驱。无法执行！为前驱。无法执行！73数数 据据 结结 构构7.5.1 拓扑排序拓扑排序第第 7 章章 图图2.有向无环图的应用有向无环图的应用

57、拓扑排序拓扑排序如何进行拓扑排序？如何进行拓扑排序？.从有向图中选取一个从有向图中选取一个没有前驱没有前驱的顶点，并输出之；的顶点，并输出之；.从有向图中从有向图中删去此顶点以及所有以它为尾的弧；删去此顶点以及所有以它为尾的弧；重复上述两步，直至重复上述两步，直至图空图空，或或者图者图不空但不空但找不到无前驱的顶点为止找不到无前驱的顶点为止。74数数 据据 结结 构构7.5.1 拓扑排序拓扑排序第第 7 章章 图图2.有向无环图的应用有向无环图的应用拓扑排序拓扑排序例如：例如：CDAGFBHECDAGFBHEACBHGD FE没有前驱的顶点没有前驱的顶点 入度为零的顶点入度为零的顶点删除顶点及

58、它的出弧删除顶点及它的出弧 弧头顶点的入度弧头顶点的入度-175数数 据据 结结 构构7.5.1 拓扑排序拓扑排序第第 7 章章 图图2.有向无环图的应用有向无环图的应用拓扑排序拓扑排序算法实现：算法实现：v2v4v1v3v5v6212345v1v2v3v4v5v663425 545 123456indegree00000011121 22376数数 据据 结结 构构7.5.1 拓扑排序拓扑排序第第 7 章章 图图2.有向无环图的应用有向无环图的应用拓扑排序拓扑排序算法实现：算法实现：v2v4v1v3v5v6212345v1v2v3v4v5v663425 545 123456indegree0

59、0000011121 223链栈：将入度为链栈：将入度为0的结点进栈的结点进栈77数数 据据 结结 构构7.5.2 关键路径关键路径第第 7 章章 图图 从源点到汇点的最长路径长度。这条路径长从源点到汇点的最长路径长度。这条路径长度最长的路径叫做关键路径（度最长的路径叫做关键路径（Critical Path）图图7-20中的中的v1-v2-v4-v5-v7就是一条关键路径，就是一条关键路径，长度为长度为6+1+9+2=18 78（浙江师范大学）图为一个用（浙江师范大学）图为一个用AOE网表示的工程。试回答：网表示的工程。试回答：（1）完成此工程，至少需要多少时间？）完成此工程，至少需要多少时间？（2）指出关键路径。）指出关键路径。（3）哪些活动加速，可以缩短完成工程所需的时间？）哪些活动加速，可以缩短完成工程所需的时间？解答：（解答：（1）至少需要时间为）至少需要时间为16。（2）为（）为（V1，V3，V5，V7，V9）。）。（3）活动）活动a2，a6，a9，a12加速，可以缩短工程所需的时间。加速，可以缩短工程所需的时间。