《数据结构与算法》第七章图资料课件.ppt
图中边图中边/ /弧的数目与顶点度的关系弧的数目与顶点度的关系G G1 1=(V=(V1 1,A,A1 1) )V V1 1=v=v1 1,v,v2 2,v,v3 3,v,v4 4 A A1 1=v=, G2=(V2,E2)V2=v1,v2,v3,v4,v5E2=(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5)niiniiniivODevIDevTDe111)()()(21图中边图中边/弧的数目与顶点度的关系弧的数目与顶点度的关系(若图中有若图中有n个顶点，个顶点，e条边条边/弧弧)2.有向图有向图G=（V，A） 从顶点从顶点v到到v1的路径是一个有向顶点序列的路径是一个有向顶点序列: v=Vi,0, Vi,1,Vi,m=v1 其中其中Vi,j-1，Vi,j A， 1jm7.2 7.2 图的存储结构图的存储结构 用用一个数组一个数组存储顶点的信息，存储顶点的信息， 用另用另一个数组一个数组存储边或弧的信息存储边或弧的信息-邻接矩阵邻接矩阵0123v1v2v3v401234南校区，南校区，105号号北一区，北一区，83号号北二区，北二区，56号号东一区，甲东一区，甲23东二区，东二区，5号号15105301220321040123v1v2v3v4G1.arcs01.adj=1方法：对每个顶点建立一个单向链表方法：对每个顶点建立一个单向链表 链接与链接与v vi i有边相连的顶点（无向图）有边相连的顶点（无向图） 或从或从v vi i出发到达的顶点（有向图）出发到达的顶点（有向图） datadata firstarcfirstarc指向该点出发到达的第一条弧指向该点出发到达的第一条弧adjvex nextarc infoadjvex nextarc info每个顶点对应一个头结点每个顶点对应一个头结点每条边每条边/ /弧对应一个结点弧对应一个结点到达顶点到达顶点 下一条边下一条边/ /弧弧 边的信息边的信息边结点边结点图中的每一弧也用一个结点表示：图中的每一弧也用一个结点表示：data firstindata firstin firstoutfirstouttailvex headvex hlink tlink infotailvex headvex hlink tlink infomark ivex ilink jvex jlink infomark ivex ilink jvex jlink infodata firstedgedata firstedge顶点：顶点：242342v1v2v3v4v5v6v7v8ABCDEFHGK1 12 23 34 45 56 67 78 89 9搜索搜索回退回退ABCDEFHGK1 12 23 34 45 56 67 79 9方法：方法： 从图中某个顶点出发（设为从图中某个顶点出发（设为v vi i），访问），访问v vi i， 从从v vi i出发，依次访问出发，依次访问v vi i的所有未被访问的邻接点，的所有未被访问的邻接点， 再从这些邻接点出发，再从这些邻接点出发， 依次访问它们的所有未被访问的邻接点依次访问它们的所有未被访问的邻接点, , 若图中仍有未被访问的顶点，若图中仍有未被访问的顶点， 从中选择一个作为起点，重复上述过程从中选择一个作为起点，重复上述过程 直到所有顶点均被访问过为止。直到所有顶点均被访问过为止。 搜索搜索ABCDEFHGK1 12 23 34 45 56 67 78 89 9ABCDEFHGK1 12 23 34 45 56 67 78 89 9对一个对一个连通图连通图G G，从图中任意一个顶点出发遍历图时，从图中任意一个顶点出发遍历图时，把把E分为分为E1 1和和E2，E1 1为为遍历过程中经过的边遍历过程中经过的边的集合，的集合，E2 2为剩余边的集合，则为剩余边的集合，则E1 1与与V V构成构成G G的极小连通图，即连的极小连通图，即连通图的一棵通图的一棵生成树生成树 若遍历为若遍历为DFSDFS，则称为，则称为深度优先生成树深度优先生成树 若遍历为若遍历为BFSBFS，则称为，则称为广度优先生成树广度优先生成树v1v2v3v4v5v6v7v8v1v2v3v4v5v6v7v8v1v2v3v4v5v6v7v8UV-Uv4v6v1v2v3v51555666342v1v31v1v31v64v42v25v53v1v31v64v42v1v31v64v25v42v1v31v64uvuvV-U 图图-邻接矩阵邻接矩阵 1 12 23 34 4U UV-UV-Uk kadjvexadjvexlowcostlowcostA A2 2A AA A6 6A A4 4AAB,C,D,EB,C,D,EadjvexadjvexlowcostlowcostA,A, adjvexadjvexlowcostlowcostadjvexadjvexlowcostlowcostadjvexadjvexlowcostlowcostv1v2v3v4v5v6v4v6v1v2v3v515556663421v1v2v3v4v5v612453v1v2v3v4v5v612v1v2v3v4v5v6123v1v2v3v4v5v61423C语言程序设计语言程序设计数据结构与算法数据结构与算法面向对象程序面向对象程序设计设计计算机网计算机网络原理络原理信息科学导论信息科学导论电路原理电路原理大学物理大学物理数字逻辑电路数字逻辑电路实验实验 组成原理实验组成原理实验操作系统操作系统汇编语言汇编语言程序设计程序设计高等数学高等数学1离散数学离散数学数据库原理数据库原理线性代数线性代数基础物理实基础物理实验验B高等数学高等数学2高等数学高等数学3C程序设计实验程序设计实验数据结构实验数据结构实验电路原理实验电路原理实验概率与数理统概率与数理统计计数字逻辑电路数字逻辑电路计算机组成计算机组成原理原理网络原理实验网络原理实验操作系统实验操作系统实验 面向对象实验面向对象实验 设设AOV网中有网中有n个顶点个顶点V1，V2，Vn， 将顶点排成这样一个线性次序：将顶点排成这样一个线性次序：Vi1，Vi2，Vin， 其中其中i1，i2，in是是1到到n的一个排列的一个排列 且若且若V ij，V ik A，则，则jk对对AOV网给出拓扑次网给出拓扑次序的过程称为序的过程称为拓扑排拓扑排序序(1)在网中选一个没有前驱的顶点且输出它在网中选一个没有前驱的顶点且输出它(2)从图中删去该顶点及所有以它为尾的弧从图中删去该顶点及所有以它为尾的弧(3)重复重复(1)(2)直到所有顶点被输出直到所有顶点被输出 或图中不存在无前驱的顶点为止或图中不存在无前驱的顶点为止。还可以利用深度优先遍历过程进行拓扑排序，。还可以利用深度优先遍历过程进行拓扑排序，按退出按退出DFSDFS的逆序为拓扑次序的逆序为拓扑次序v1v2v3v4v5v6123456拓扑次序为：拓扑次序为：v6、v1、v4、v3、v5、v2V Vi i表示在此表示在此之前的活动之前的活动已完成，在已完成，在此之后的活此之后的活动可以开始动可以开始a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=412345买面粉买面粉3买鸡蛋买鸡蛋3买白菜买白菜4买熟食买熟食667剁馅剁馅5切切2和面和面2煮鸡蛋煮鸡蛋1包饺子包饺子4最短要多久才能包好饺子最短要多久才能包好饺子, ,开始聚餐开始聚餐? ?a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4 计算的方法：计算的方法：（1 1）ve(0)=0ve(0)=0（2 2）按拓扑顺序计算：）按拓扑顺序计算： ),()()(1,.,2, 1,jidutiveMaxjvenjTjii 其中其中T T是所有以第是所有以第j j个顶点为头的弧的集合个顶点为头的弧的集合i1i2i3j（3 3）vl(n-1)=ve(n-1)vl(n-1)=ve(n-1)（4 4）按逆拓扑顺序计算：）按逆拓扑顺序计算： 其中其中S S是所有以第是所有以第i i个顶点为尾的弧的集合个顶点为尾的弧的集合 ),()()(0,.,3,2,jidutjvlMinivlnniSjijj1j2j3i（5 5）根据各顶点的）根据各顶点的veve和和vlvl的值的值 计算每条弧计算每条弧s s的的e(s)e(s)和和l(s)l(s)a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4ve(3)=5ve(4)=7ve(7)=14ve(8)=18ve(0)=0ve(5)=7ve(6)=16ve(2)=4ve(1)=6v0v560v1v2v3v410030101050520v0v5v1v2v3v430101020存储结构存储结构用带权的邻接矩阵用带权的邻接矩阵arcsarcs表示带权有向图表示带权有向图arcsij= arcsij= V A A V 上的权值上的权值 V A A算法算法(1)(1)设设S S为已找到从为已找到从v v出发的最短路径的终点集合出发的最短路径的终点集合, , 初值初值S=S= Di Di表示从表示从v v到到V Vi i的最短路径的长度的最短路径的长度 若若v A,DiA,Di为从为从v v到到V Vi i上的权上的权, ,否则为否则为 即：即：Di=arcsLocateVex(G,v),i, VDi=arcsLocateVex(G,v),i, Vi i V V(2)选择选择Vj，使得，使得 Dj=minDi| Vi V-S 并修改并修改S: S=S j Vj就是一条从就是一条从v出发的最短路径的顶点出发的最短路径的顶点(3)修改从修改从v出发到集合出发到集合V-S上任一点上任一点Vk可到达的最短路可到达的最短路径径 即如果即如果 Dj+arcsjkDk 则：则： Dk=Dj+arcsjk(如果如果S为已求得最短路径的终点集合为已求得最短路径的终点集合,则下一条最短路则下一条最短路径或者是弧径或者是弧, 或者是从或者是从v到到Vk加上弧加上弧,其中其中 Vk S）(4)重复重复(2)(3)共共n-1次次,求得从求得从v到图中其余各顶点的最到图中其余各顶点的最短路径短路径终点终点从从V V0 0到各终点到各终点D D值和最短路径的求解过程值和最短路径的求解过程V V1 1V V2 2V V3 3V V4 4V Vj jV V5 5i=1V V2 2 1010(V(V0 0 ,V,V2 2) )3030(V(V0 0 ,V,V4 4) )100100(V(V0 0 ,V,V5 5) )VV0 0 ,V,V2 2 S S 3030(V(V0 0 ,V,V4 4) )100100(V(V0 0 ,V,V5 5) )6060(V(V0 0 ,V,V2,2,V,V3 3) )VV0 0 ,V,V2 2,V,V4 4 V V4 4i=2 i=55050(V(V0 0 ,V,V4 4 ,V,V3 3) )9090(V(V0 0 ,V,V4 4 ,V,V5 5) )V V3 3 i=3VV0 0,V,V2 2,V,V3 3,V,V4 4 V V5 56060(V(V0 0 ,V,V4 4 ,V,V3 3 ,V,V5 5) ) i=4VV0 0,V,V2 2,V,V3 3,V,V4 4,V,V5 5 for(v=0; vG.vexnum; +v) finalv = FALSE; Dv = G.arcsv0v; for(w=0; wG.vexnum; +w) Pvw = FALSE; / 设空路径设空路径 if (DvINFINITY) pvv0=TRUE; pvv = TRUE; / forDv0 = 0; finalv0 = TRUE; / 初始化，初始化，v0顶点属于顶点属于S集集若若w w是从是从v0v0到到v v最短路径上的顶点最短路径上的顶点, ,则则pvwpvw为为TRUETRUE已经求得从已经求得从v0v0到到v v的最短路径的最短路径,finalv,finalv为为TRUETRUE方法一方法一:每次以一个顶点为源点每次以一个顶点为源点,重复执行迪杰斯特拉重复执行迪杰斯特拉方法方法方法二：方法二：,求顶点对求顶点对的最短路径：的最短路径：(1)的路径长度与的路径长度与比较，小者为从比较，小者为从Vi到到Vj的中间顶点序号不大于的中间顶点序号不大于0的最短路径的最短路径(2) 加入顶点加入顶点V1, 设设和和为为 中间顶点序号不大于中间顶点序号不大于0的最短路径，的最短路径， 比较比较和和， 小者为从小者为从Vi到到Vj的中间顶点序号不大于的中间顶点序号不大于1的最短路径的最短路径定义定义n n阶方阵序列：阶方阵序列：表示从表示从V Vi i到到V Vj j的中间顶点序号不大于的中间顶点序号不大于k k的最短路径的最短路径的长的长, ,min)1()1()1(10)()1(jkDkiDjiDjiDjiarcsjiDkkknkk的的最最短短路路径径长长度度到到即即为为从从ji)1n(vv ji D v0v1v2641132(3)(3)依次加入依次加入V V2 2,V,V3 3, ,V,Vn-1n-1, , 共经过共经过n n次比较后，求得次比较后，求得V Vi i到到V Vj j的最短路径的最短路径void ShortestPath_FLOYD(Mgraph G, PathMatrix &p , DistancMatrix &D )for (v=0; vG.vexnum; +v) for (w=0; wG.vexnum; +w) Dvw = G.arcvw; for(u=0; uG.vexnum; +u) Pvwu = FALSE; if (Dvw INFINITY) Pvwv = TRUE; Pvww = TRUE; / forfor (u=0;uG.vexnum; +u) for (v=0; vG.vexnum; +v) for (w=0; wG.vexnum; +w) if (Dvu+DuwDvw) /从从v v经经u u到到w w的一条路径更短的一条路径更短 Dvw = Dvu + Duw; for (i=0; iG.vexnum; +i) Pvwi = Pvui | Puwi; / if / ShortestPath_FLOYDABC641132765
