深度优先搜索算法最小生成树关键路径动态演示.课件.ppt

1、 v5 v1 v2 v3 v4 3 1 4 2 4 3 2 0 2 1 0 1 01234vertex firstedgeadjvex next顶点表顶点表边表边表V3V1V4V5V2G1void DFS1 (AdjGraph* G, int i)/以以vi为出发点时对邻接表表示的图为出发点时对邻接表表示的图G进行进行搜索搜索 EdgeNode *p; coutadjvex if ( ! visited padjvex ) /若若vj尚未访问尚未访问 DFS1(G, padjvex); / 则以则以vj为出发点先深搜索为出发点先深搜索 p=pnext; /DFS1void DFS2 ( MTG

2、raph *G, int i )/ 以以vi为出发点对矩阵为出发点对矩阵(0,1矩阵矩阵)表示的图表示的图G进行深度优先搜索进行深度优先搜索 int j; coutGvexlisti; /访问定点访问定点vi visitedi=TRUE; /标记标记vi已访问已访问 dfni=count; /对对vi进行编号进行编号 count +; /下一个顶点的编号下一个顶点的编号 for( j=0; jGn; j+) /依次搜索依次搜索vi的邻接点的邻接点 if(Gedgeij = 1)& ! visitedj ) /若若vj尚未访问尚未访问 DFS2( G, j );/DFS20123=0101101

3、001011010G.edge最小生成树演示1545235666abdcef算法采用邻接矩阵来存储图。1 a2 b3 c4 d5 e6 fa b cd e fa 6 1 5 b 6 5 3 c1 5 5 6 4d 5 5 2e 3 6 6f 4 2 6 用一个数组用一个数组L L来存储各个顶点到当前最小生成树来存储各个顶点到当前最小生成树的最短的最短 距离。距离。uvlength123456u u为顶点，为顶点，v v为当前生成树上为当前生成树上距离顶点距离顶点u u最近的顶点，最近的顶点，lengthlength为边（为边（u u，v v）的权值。）的权值。L：初始化数组初始化数组L L：u

4、vlength123456初始情况下，生成树中只有初始情况下，生成树中只有一个顶点一个顶点a a，并令其到自身，并令其到自身的距离为的距离为0 0。L：1545235666abdcef初始化数组L：uvlength1aa02ba63ca14da55ea6f a在具体实现时， 可以用一个比较大的数来表示。L：1545235666abdcef开始生成最小生成树：uvlength1aa02ba63ca14da55ea6f a接下来，选择距离生成树最近的顶点。方法是遍历数组L，找出length不等于0，且为最小的距离。length等于0表示当前顶点已经被选入生成树。L：1545235666abdcef

5、uvlength1aa02ba63ca14da55ea6f ac被选中，加入生成树中。并更新数组L。L：1545235666abdcefuvlength1aa02ba63ca04da55ea6f aL：1545235666abdcef更新数组L，c被选入生成树，故对应项的Length应该赋值为0uvlength1aa02ba63ca04da55ea6f a更新剩余顶点到当前生成树的最短距离。以顶点b为例。c加入生成树前，b到生成树的最短距离已经在数组L中保存，c加入后，比较L中数据和边（b，c）的权值，如果后者小，说明b到生成树的距离变小了，应该更新，否则不变。L：1545235666abdc

6、efuvlength1aa02ba63ca04da55ea6f aba=6ec=6,故更新L：1545235666abdcefuvlength1aa02bc53ca04da55ec66f aL：1545235666abdcefuvlength1aa02bc53ca04da55ec66f afa= fc=4,故更新L：1545235666abdcefuvlength1aa02bc53ca04da55ec66f c4更新完毕！L：1545235666abdcefuvlength1aa02bc53ca04da55ec66f c4选择距离当前生成树最近的顶点f。加入到生成树中并更新。、L：154523

7、5666abdcefuvlength1aa02bc53ca04da55ec66f c0L：1545235666abdcefuvlength1aa02bc53ca04da55ec66f c0bc=5df=2,需要更新L：1545235666abdcefuvlength1aa02bc53ca04df25ec66f c0bc=5df=2,需要更新ec=6=ef=6,不用更新L：1545235666abdcefuvlength1aa02bc53ca04df25ec66f c0选择距离生成树最小的顶点d。加入到生成树中，并更新L：1545235666abdcefuvlength1aa02bc53ca04

8、df05ec66f c0L：1545235666abdcefuvlength1aa02bc53ca04df05ec66f c0bc=5bd= ,不用更新ec=6eb=3,需要更新L：1545235666abdcefuvlength1aa02bc03ca04df05eb36f c0L：1545235666abdcefuvlength1aa02bc03ca04df05eb36f c0L：1545235666abdcef选择距离生成树最近的顶点e加入生成树中，并更新uvlength1aa02bc03ca04df05eb06f c0L：1545235666abdcef选择距离生成树最近的顶点e加入生成

9、树中，并更新uvlength1aa02bc03ca04df05eb06f c0L：1545235666abdcef此时全部顶点都被选入了生成树，最小生成树已经求出来了关键路径演示abceghk64521187244dfa b c d e f g h kvevl00000 00006457115 715 14 18181818181818181816 1486610807a b c d e f g h kvevl064577 15 14 181814161078660ab ac ad be ce df eg eh fh gk hk权权6 4 5 1 1 2 8 7 4 2 4el00 0 64 5 7 77 15 1414160 23 66 8 87 10