图的基本概念图的存储结构图的遍历最小生成树最短路径ppt课件.ppt

《图的基本概念图的存储结构图的遍历最小生成树最短路径ppt课件.ppt》由会员分享，可在线阅读，更多相关《图的基本概念图的存储结构图的遍历最小生成树最短路径ppt课件.ppt（56页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 图的基本概念 图的存储结构 图的遍历 最小生成树 最短路径 拓扑排序 关键路径源 点 终 点 最 短 路 径路 径 长 度 v0 v1(v0, v1)10 v2 (v0, v1, v2) (v0, v3, v2) 60 50 v3(v0, v3)30 v4(v0, v4)(v0, v3, v4) (v0, v3, v2, v4)100 90 60算法的基本思想算法的基本思想 设置并逐步扩充一个集合设置并逐步扩充一个集合S S，存放已求，存放已求出的最短路径的顶点，则尚未确定最短路径出的最短路径的顶点，则尚未确定最短路径的顶点集合是的顶点集合是V-SV-S， 为了直观起见，我们设想为了直观起见

2、，我们设想S S中顶点均被中顶点均被涂成红色，涂成红色，V-SV-S中的顶点均被涂成蓝色。算中的顶点均被涂成蓝色。算法初始化时，红点集中仅有一个源点，以后法初始化时，红点集中仅有一个源点，以后每一步都是按最短路径长度递增的顺序，逐每一步都是按最短路径长度递增的顺序，逐个地把蓝点集中的顶点涂成红色后，加入到个地把蓝点集中的顶点涂成红色后，加入到红点集中。红点集中。算法粗框：算法粗框：while ( S 中的红点数中的红点数 n ) 在当前蓝点集中选择一个最短路径长度最短的在当前蓝点集中选择一个最短路径长度最短的 蓝点扩充到蓝点集中；蓝点扩充到蓝点集中；那么，如何在蓝点集中选择一个最短那么，如何在

3、蓝点集中选择一个最短路径长度最短的蓝点呢？路径长度最短的蓝点呢？注意：这种蓝点所对应的最短路径上注意：这种蓝点所对应的最短路径上，除终点外，其余顶点都是红点。为此，除终点外，其余顶点都是红点。为此，对于图中每一个顶点对于图中每一个顶点 i i ，都必须记住从，都必须记住从v v 到到i i 、且中间只经过红点的最短路径的长、且中间只经过红点的最短路径的长度，并将此长度记作度，并将此长度记作 i i 的的距离值距离值。 开始时，红点集只有一个源点开始时，红点集只有一个源点v v，初始，初始蓝点集中的蓝点蓝点集中的蓝点j j的距离值的距离值DjDj均为有向边均为有向边上的权值。上的权值。 用数组用

4、数组D(n)D(n)来存放来存放n n个顶点的距离值。个顶点的距离值。若当前蓝点集中具有最小距离值的蓝点是若当前蓝点集中具有最小距离值的蓝点是k k，则其距离值则其距离值D(k)D(k)是是k k的最短路径长度的最短路径长度，并，并且且k k是蓝点集中最短路径长度最短的顶点是蓝点集中最短路径长度最短的顶点。证明：证明： （距离值（距离值D(k)D(k)是是k k的最短路径长度）的最短路径长度）若若D(k)D(k)不是不是k k的最短路径长度，则必存在另外一条的最短路径长度，则必存在另外一条从源点从源点v v到到k k的路径的路径P P，其长度小于，其长度小于D(k)D(k)。由距离值的定。由距

5、离值的定义可知，路径义可知，路径P P上必然包含一个或多个蓝点作为中间点上必然包含一个或多个蓝点作为中间点。假设从源点沿。假设从源点沿P P向前第一次碰到的蓝点是向前第一次碰到的蓝点是x x，则，则P P上从上从源点源点v v到到x x的这一段路径的长度，显然不小于的这一段路径的长度，显然不小于x x的距离值的距离值D(x)D(x)。而。而P P上从上从x x到终点到终点k k所经过的边上，其权值均为非所经过的边上，其权值均为非负实数，所以负实数，所以D(x)=PD(x)=P的长度。又因为的长度。又因为P P的长度的长度D(k)(D(k)(这是假设前提这是假设前提) )，于是有下述不等式：，于

6、是有下述不等式：D(x) = PD(x) = P的长度的长度 D(k) D(k)由此可知：由此可知：D(x) D(k)D(x) = D(k)= D(k)。若。若i i的最短路径的最短路径P P包含其它蓝点作为中间点，包含其它蓝点作为中间点，设设P P上第一个蓝点是上第一个蓝点是j j，则，则P P上从上从v v到到j j的路径长度就是的路径长度就是j j的距离值的距离值D(j)D(j)。显然，。显然，D(j)=D(k)D(j)=D(k)，而，而P P的长度的长度= =D(j)+jD(j)+j到到i i的长度，因为的长度，因为j j到到i i的长度为非负实数，所以的长度为非负实数，所以 P P的

7、长度的长度=D(k)=D(k)。由此可知蓝点集中任意顶点。由此可知蓝点集中任意顶点i i的最短的最短路径长度都不会小于路径长度都不会小于k k的最短路径长度的最短路径长度D(k)D(k)。 扩充红点集的方法：每一步只要在当前蓝点集中扩充红点集的方法：每一步只要在当前蓝点集中选择一个具有最小的距离值的蓝点选择一个具有最小的距离值的蓝点k k扩充到红点集合中扩充到红点集合中，k k被涂成红色之后，剩余的蓝点的距离值可能由于增被涂成红色之后，剩余的蓝点的距离值可能由于增加了新红点加了新红点k k而发生变化（即减少）。因此必须调整当而发生变化（即减少）。因此必须调整当前蓝点集中各蓝点的距离值。前蓝点集

8、中各蓝点的距离值。算法框架算法框架：S = v;置初始蓝点集中各蓝点的距离值；置初始蓝点集中各蓝点的距离值；while ( S中红点数中红点数 n ) 在当前蓝点集中选择距离值最小的顶点在当前蓝点集中选择距离值最小的顶点k； S = S + k; /* 将将k涂成红色加入红点集涂成红色加入红点集 */ 调整剩余蓝点的距离值；调整剩余蓝点的距离值； 如何调整剩余蓝点的距离值呢？如何调整剩余蓝点的距离值呢？ 若新红点若新红点k k加入红点集加入红点集S S后，使得某个蓝点后，使得某个蓝点j j的距离值的距离值D(j)D(j)减少，则必定是由于存在一条从源减少，则必定是由于存在一条从源点点v v途径

9、新红点途径新红点k k最终到达蓝点最终到达蓝点j j且中间只经过红且中间只经过红点的、新的最短路径点的、新的最短路径P Pvkjvkj，它的长度小于从源点，它的长度小于从源点v v到达到达j j且中间只经过老红点（即步包含且中间只经过老红点（即步包含k k）的原最）的原最短路径短路径P Pvjvj的长度的长度D(j)D(j)。由于。由于P Pvkjvkj是一条中间只经是一条中间只经过红点的最短路径，所以，它的前一段从过红点的最短路径，所以，它的前一段从v v到到k k的的路径必定是路径必定是k k的最短路径，其长度为的最短路径，其长度为D(k)D(k)；它的；它的后一段从后一段从k k到到j

10、j的路径的路径P Pkjkj只可能有两种情形：其一只可能有两种情形：其一是由是由k k经过边经过边直达蓝点直达蓝点j j；其二是从；其二是从k k出发再出发再经过经过S S中若干老红点后到达中若干老红点后到达j j。用反正法证明后一种情形是不可能的。用反正法证明后一种情形是不可能的。 假设从源点假设从源点v v出发，经过红点出发，经过红点k k、老红点、老红点x x，最后到达蓝，最后到达蓝点点j j的新最短路径的新最短路径P Pvkxjvkxj的长度小于原的长度小于原D(j)D(j)。因为。因为x x比比k k先加入先加入红点集红点集S S，故，故D(x)=D(k)D(x)=D(k)，又因为权

11、值非负，所以从，又因为权值非负，所以从v v到到x x的的路径路径P Pvxvx的长度不大于从的长度不大于从v v经经k k到到x x的路径的路径P Pvkxvkx的长度，即的长度，即 length(Plength(Pvkvk)=D(x)=D(k)+length(P)=D(x)=D(k)+length(Pkxkx)=length(P)=length(Pvkxvkx) )因此从因此从v v经经x x到到j j的路径长度的路径长度: : length(P length(Pvxjvxj)=length(P)=length(Pvkvk)+length(P)+length(Pxjxj) )不大于从不大于

12、从v v经经k k、x x到到j j的新路径长度的新路径长度 length(Plength(Pvkxjvkxj)=length(P)=length(Pvkxvkx)+length(P)+length(Pxjxj) )又因为又因为P Pvxjvxj中间只经过老红点，所以中间只经过老红点，所以P Pvxjvxj的长度不大于的长度不大于D(j)D(j)的值的值，由此可得：由此可得： D(j)=length(PD(j)=length(Pvxjvxj)=length(P)=length(Pvkxjvkxj) )这与新路径这与新路径P Pvkxjvkxj的长度小于原的长度小于原D(j)D(j)值的假设相矛

13、盾！因此值的假设相矛盾！因此，使得，使得D(j)D(j)值减小的新路径比必是先经过老红点到达值减小的新路径比必是先经过老红点到达k k，然，然后经过边后经过边直达蓝点直达蓝点j j的，它得长度是的，它得长度是D(k)+D(k)+边边上上的权。的权。 由此得到调整距离值的方法：当顶点由此得到调整距离值的方法：当顶点k k从蓝点集转移到从蓝点集转移到红点集时，对蓝点集扫描检查，若某蓝点红点集时，对蓝点集扫描检查，若某蓝点j j的原距离值的原距离值D(j)D(j)大于新路径的长度大于新路径的长度D(k)+D(k)+边边上的权，则将上的权，则将D(j)D(j)修改成修改成此长度值。此长度值。 为了同时

14、得到路径，设置一个路径向量为了同时得到路径，设置一个路径向量Pn,Pn,其中其中PiPi表示从源点到达表示从源点到达i i点的最短路径上该点的前驱顶点。点的最短路径上该点的前驱顶点。蓝点蓝点j蓝点蓝点k红点集红点集S源点源点vx循环循环红点集红点集k+1D0D4PP4初始化初始化44,34,3,54,3,5,14,3,5,1,2-3512max max 20 0 60max max 20 0 30max max 20 0 30max max 20 0 30max max 20 0 300 0 4 0 40 0 4 0 30 0 4 0 30 0 4 0 30 0 4 0 35010301020

15、60100 max 1 max 2 20 3 - 4 0 4 30 5 - 3 - 410301020float Dn;int Pn,Sn;DIJKSTRA(float Cn, int v) int i,j,k,v1,pre; int min,max=60,inf=80; v1=v-1; for (i=0;in;i+) Di=Cv1i; if (Di!=max) Pi=v; else Pi=0; for (i=0;in;i+) Si=0; Sv1=1; Dv1=0; for (i=0;in-1;i+) min=inf; for (j=0;jn;j+) if (!Sj)&(Djmin) min=

16、Dj; k=j; Sk=1; for (j=0;jDk+Ckj) Dj=Dk+Ckj; Pj=k+1; for (i=0;in;i+) printf(“%fn%d”,Di,i+1); pre=pi; while (pre!=0) printf(“-%d”,pre); pre=Ppre-1; 算法说明算法说明对于顶点对于顶点i i和和j j：1 1、首先，考虑从、首先，考虑从i i到到j j是否有以顶点是否有以顶点1 1为中间为中间点的路径，：点的路径，：i i，1 1，j j，即考虑图中是否有，即考虑图中是否有边边和和，若有，则新路径，若有，则新路径i i，1 1，j j的长度是的长度是Ci1

17、+C1jCi1+C1j，比较路径，比较路径i i，j j和和i i，1 1，j j，的长度，并以较短者为当前所，的长度，并以较短者为当前所求得的最短路径，。该路径是中间点序号不求得的最短路径，。该路径是中间点序号不大于大于1 1的最短路径。的最短路径。所有顶点对之间的最短路径所有顶点对之间的最短路径2 2、其次，考虑从、其次，考虑从i i到到j j是否包含顶点是否包含顶点2 2为中间为中间点的路径：点的路径：i i，.，2 2，.，j j，若没有，则，若没有，则从从i i到到j j的最短路径仍然是第一步中求出的，的最短路径仍然是第一步中求出的，即从即从i i到到j j的中间点序号不大于的中间点

18、序号不大于1 1的最短路径；的最短路径；若有，则若有，则i i，.，2 2，.，j j可分解成两条路可分解成两条路径径i i，.，2 2和和2 2，.，j j，而这两条路径是，而这两条路径是前一次找到的中间点序号不大于前一次找到的中间点序号不大于1 1的最短路径的最短路径，将这两条路径相加就得到路径，将这两条路径相加就得到路径i i，.，2 2，.，j j的长度，将该长度与前一次求出的从的长度，将该长度与前一次求出的从i i到到j j的中间点序号不大于的中间点序号不大于1 1的最短路径长度比的最短路径长度比较，取其较短者作为当前求得的从较，取其较短者作为当前求得的从i i到到j j的中的中间点

19、序号不大于间点序号不大于2 2的最短路径。的最短路径。3 3、然后，再选择顶点、然后，再选择顶点3 3加入当前求得的从加入当前求得的从i i到到j j中中间点序号不大于间点序号不大于2 2的最短路径中，按上述步骤进行的最短路径中，按上述步骤进行比较，从未加入顶点比较，从未加入顶点3 3作中间点的最短路径和加入作中间点的最短路径和加入顶点顶点3 3作中间点的新路径中选取较小者，作为当前作中间点的新路径中选取较小者，作为当前求得的从求得的从i i到到j j的中间点序号不大于的中间点序号不大于3 3的最短路径。的最短路径。依次类推，直到考虑了顶点依次类推，直到考虑了顶点n n加入当前从加入当前从i

20、i到到j j的最的最短路径后，选出从短路径后，选出从i i到到j j的中间点序号不大于的中间点序号不大于n n的最的最短路径为止。由于图中顶点序号不大于短路径为止。由于图中顶点序号不大于n n，所以从，所以从i i到到j j的中间点序号不大于的中间点序号不大于n n的最短路径，已考虑了的最短路径，已考虑了所有顶点作为中间点的可能性。因而它必是从所有顶点作为中间点的可能性。因而它必是从i i到到j j的最短路径。的最短路径。算法的基本思想就是：算法的基本思想就是：从初始的邻接矩阵从初始的邻接矩阵A A0 0开始，递推地生成矩阵序列开始，递推地生成矩阵序列A A1 1，A A2 2，.，A An

21、n0jiCjiA,min1jkAkiAjiAjiAkkkk显然，显然，A A中记录了所有顶点对之间的最短路径长度。中记录了所有顶点对之间的最短路径长度。若要求得到最短路径本身，还必须设置一个路径矩若要求得到最短路径本身，还必须设置一个路径矩阵阵PnnPnn，在第，在第k k次迭代中求得的次迭代中求得的pathijpathij，是，是从从i i到到j j的中间点序号不大于的中间点序号不大于k k的最短路径上顶点的最短路径上顶点i i的的后继顶点。算法结束时，由后继顶点。算法结束时，由pathijpathij的值就可以的值就可以得到从得到从i i到到j j的最短路径上的各个顶点。的最短路径上的各个

22、顶点。Floyd算法算法int pathnn;FLOYD(float An,float Cn) int i,j,k,next; int max=160; for (i=0,in,i+) for (j=0;jn;j+) if (Cij!=max) pathij=j; else pathij=0; Aij=Cij; for (k=0;kn;k+) for (i=0;in;i+) for (j=0;j(Aik+Akj) Aij=Aik+Akj; pathij=pathik; for (i=0;in;i+) for (j=0;j%d”,next+1); next=pathnextj; printf(“

23、-%d”,j+1); 50103010206010006002010050010030100A00600201005001003060100A2030020100605001003060100A3030020100605001003050100A4学生课程学习工程图学生课程学习工程图abcdef 为了便于考察每个顶点的入度，在顶点表中增加为了便于考察每个顶点的入度，在顶点表中增加一个入度域，同时设置一个栈来存储所有入度为一个入度域，同时设置一个栈来存储所有入度为0 0 的的顶点。在进行拓扑排序之前，只要对顶点表扫描一遍顶点。在进行拓扑排序之前，只要对顶点表扫描一遍，将所有入度为，将所有入度为0

24、 0 的顶点都推入栈中，一旦排序过程的顶点都推入栈中，一旦排序过程中出现新的入度为中出现新的入度为0 0 的顶点，也同样将其推入栈中。的顶点，也同样将其推入栈中。v10v22nullv31v42v53nullv60。 。 。 。 123456出边表出边表1、扫描顶点表，将入度为、扫描顶点表，将入度为0 的顶点入栈；的顶点入栈；2、while ( 栈非空栈非空 ) 将栈顶顶点将栈顶顶点v弹出并输出之；弹出并输出之； 检查检查v的出边，将每条出边的出边，将每条出边终点终点u的入度减的入度减1， 若若u的入度变为的入度变为0，则把，则把u推入栈；推入栈； 3、若输出的顶点数小于、若输出的顶点数小于n

25、，则输出，则输出“有回路有回路”；否则拓；否则拓扑扑 排序正常结束。排序正常结束。拓扑排序算法框架拓扑排序算法框架 在算法具体实现时，上述链栈无须占有在算法具体实现时，上述链栈无须占有额外的空间，而是利用顶点表中值为额外的空间，而是利用顶点表中值为0 0 的入的入度域来存放链栈的指针（用下标值模拟）。度域来存放链栈的指针（用下标值模拟）。因为顶点域中已经存入有相应的顶点，故入因为顶点域中已经存入有相应的顶点，故入栈时只需修改相应的指针。栈时只需修改相应的指针。021230021231021121014021toptoptoptop=0123456044011044011044001044001

26、toptoptop123456拓扑排序算法拓扑排序算法typedef int datatype;typedef int vextype;typedef struct node /*边表结点定义边表结点定义*/ int adjvex; struct node *next; edgenode edgenode; ; typedef struct /*顶点表结点定义顶点表结点定义*/ vextype vertex int id; edgenode *link vexnode;vexnode dign;TOPOSORT(vexnode dig) int i,j,k,m=0,top=-1; edgeno

27、de *p; for (i=0;iadjvex; digk.id-; if (digk.id=0) digk.id=top; top=k; p=p-next; if (mn) printf(“nThe network has a cyclen”); 算法分析算法分析 设设AOVAOV网有网有n n个顶点，个顶点，e e条边。初始建立条边。初始建立入度为入度为0 0 的顶点栈，要检查所有顶点一次的顶点栈，要检查所有顶点一次，执行时间为，执行时间为O(n)O(n)；排序中，若；排序中，若AOVAOV网无回网无回路，则每个顶点入、出栈各一次，每个边路，则每个顶点入、出栈各一次，每个边表结点被检查一次

28、，执行时间为表结点被检查一次，执行时间为O(n+e)O(n+e)，所以总的时间复杂度为所以总的时间复杂度为O(n+e)O(n+e)。 , ) ,( jiiVVduriVemaxjVe, ) ,( jijVVdurjVlminiVlv5v1v2v3v4v6v7v8v9465112974426405771614181814108661670v5v1v2v3v4v6v7v8v9465112974426405771614181814108661670活动活动1-21-31-42-53-54-65-75-86-87-98-9e0006457771614l02366877101614e-l02302300

29、300v5v1v2v7v8v9619742607161418181461670求关键路径的算法求关键路径的算法typedef structtypedef struct node1 / node1 /* * 边表结点定义边表结点定义 * */ / int adjvexint adjvex; /; /* * 邻接点域邻接点域 * */ / int dut int dut; /; /* * 权值权值 * */ / struct struct node1 node1 * *next; /next; /* * 链域链域 * */ / edgenode1; edgenode1;typedef struct

30、typedef struct node2 / node2 /* *顶点表结点定义顶点表结点定义* */ / vextypevextype vertex; / vertex; /* * 顶点信息顶点信息 * */ / int int id; / id; /* * 入度入度 * */ / edgenode1 edgenode1 * *link; /link; /* * 边表头指针边表头指针 * */ / vexnode1; vexnode1;vexnode1 dign;vexnode1 dign; / /* * 邻接表邻接表 * */ /CRITICALPATH(vexnode1 dig)CRIT

31、ICALPATH(vexnode1 dig) int int i,j,k,m; i,j,k,m; int int front=-1; rear=-1; front=-1; rear=-1; / /* *顺序队列首位指针置初值顺序队列首位指针置初值* */ / int tpordn,vln,ve int tpordn,vln,ven;n; int lmaxsize,emaxsize int lmaxsize,emaxsize; edgenode1 edgenode1 * *p;p; for (i=0;in;i+) for (i=0;in;i+) ve vei=0; i=0; / /* *各事件最

32、早发生时间置为各事件最早发生时间置为0 0* */ / for (i=0;in;i+) for (i=0;iadjvex k=p-adjvex; ; digk.id-; digk.id-; / /* *入度减入度减1 1* */ / if (vej+p-dutve if (vej+p-dutvek)k) vek=vej+p-dut vek=vej+p-dut; ; / /* *计算最早发生时间计算最早发生时间* */ / if (digk.id=0) if (digk.id=0) tpord tpord+rear=k; +rear=k; / /* *新的入度为新的入度为0 0的顶点入队的顶点入

33、队* */ / p=p-next; p=p-next; / /* *找下一条边找下一条边* */ / if (mn) if (mn) / /* *网中有回路，终止算法网中有回路，终止算法* */ / printf printf( (“The AOE network has a cyclenThe AOE network has a cyclen”);); return(0); return(0); for (i=0;in;i+) for (i=0;i=0;i-) for (i=n-1;i=0;i-) / /* *按拓扑序列的逆序取顶点按拓扑序列的逆序取顶点* */ / i=tpord i=tp

34、ordi;i; p=digj.link; p=digj.link; / /* *取出边表上的第一个表结点取出边表上的第一个表结点* */ / while (p) while (p) k=p-adjvex k=p-adjvex; ; if (vlk-p-dut)dut)dut vlj=vlk-p-dut; ; p=p-next; p=p-next; / /* *找下一条边找下一条边* */ / i=0; i=0; / /* *边计数器置初值边计数器置初值* */ / for (j=0;jn;j+) for (j=0;jadjvex k=p-adjvex; ; e+i=ve e+i=vej;j;

35、li=vlk-p-dut li=vlk-p-dut; ; printf printf( (“%dt%dt%dt%dt%dt%dt%dt%dt%dt%dt”, , / /* *输出信息输出信息* */ / digj.vertex+1, digj.vertex+1, digk.vertex+1,ei,li,li-ei); digk.vertex+1,ei,li,li-ei); if (li=ei) if (li=ei) / /* *关键活动关键活动* */ / printf printf( (“CRITICAL ACTIVITYnCRITICAL ACTIVITYn”);); p=p-next; p=p-next;