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

vertex firstedge

0 1 2 3 4

v1 v2 v3 v4 v5 顶点表

3 4 4 2 2

adjvex next 1 ^2 3 0 1 0 1

^ ^

^ ^V1 V2 V3 V4 V5

边表 G1

void DFS1 (AdjGraph* G, int i) //以vi为出发点时对邻接表表示的图 进行深度优先搜索 以 为出发点时对邻接表表示的图 为出发点时对邻接表表示的图G进行 { EdgeNode *p; cout<<G→vexlist[i].vertex;//访问顶点 访问顶点vi; 访问顶点 visited[i]=TRUE; //标记 已访问 标记vi已访问 标记 dfn[i]=count++; //对vi进行编号 对 进行编号 p=G→vexlist[i].firstedge; //取vi边表的头指针 取 边表的头指针 while( p ) { //依次搜索 的邻接点 这里 j=p->adjvex 依次搜索vi的邻接点 依次搜索 的邻接点vj, if ( ! visited [ p→adjvex ] ) //若vj尚未访问 若 尚未访问 DFS1(G, p→adjvex); // 则以 为出发点先深搜索 则以vj为出发点先深搜索 p=p→next; } } //DFS1

void DFS2 ( MTGraph *G, int i ) // 以vi为出发点对矩阵 为出发点对矩阵(0,1矩阵 表示的图 进行深度优先搜索 矩阵)表示的图 为出发点对矩阵 矩阵 表示的图G进行深度优先搜索 { int j; cout<<G→vexlist[i]; //访问定点 访问定点vi 访问定点 visited[i]=TRUE; dfn[i]=count; count ++; //标记 已访问 标记vi已访问 标记 //对vi进行编号 对 进行编号 //下一个顶点的编号 下一个顶点的编号

0 1 3 2

for( j=0; j<G→n; j++) //依次搜索 的邻接点 依次搜索vi的邻接点 依次搜索 if((G→edge[i][j] == 1)&& ! visited[j] ) //若vj尚未访问 若 尚未访问 DFS2( G, j ); }//DFS2

0 G.edge = 1 0 1

1 0 1 0

0 1 0 1

1 0 1 0

最小生成树演示

算法采用邻接矩阵来存储图。 b 3

6 5 6 e

a 1 5 c 4 6

5 d 2 f

1 2 3 4 5 6

a b c d e f

a b c d e f

a ∞ 6 1 5 ∞ ∞

b 6 ∞ 5 ∞ 3 ∞

c 1 5 ∞ 5 6 4

d 5 ∞ 5 ∞ ∞ 2

e ∞ 3 6 ∞ ∞ 6

f ∞ ∞ 4 2 6 ∞

用一个数组L 用一个数组L来存储各个顶点到当前最小生成树 距离。 的最短 距离。L: u v length

1 2 3 4 5 6

u为顶点，v为当前生成树上 为顶点， 距离顶点u最近的顶点， 距离顶点u最近的顶点， length为边 为边( 的权值。 length为边(u,v)的权值。

初始化数组L 初始化数组L:6L: u v length

a 1 5 6 5 c 4 6

5 d 2 f

b 3 e

1 2 3 4 5 6

初始情况下， 初始情况下，生成树中只有 一个顶点a 一个顶点a,并令其到自身 的距离为0 的距离为0。

初始化数组L:6L: u v a a a a a a length 0 6 1 5

a 1 5 6 5 c 4 6

5 d 2 f

b 3 e

1 2 3 4 5 6

a b c d e f

∞ ∞

在具体实现时， ∞可以用一个比较大的数来表示。

开始生成最小生成树：6L: u v a a a a a a length 0 6 1 5

a 1 5 6 5 c 4 6

5 d 2 f

b 3 e

1 2 3 4 5 6

a b c d e f

∞ ∞

接下来，选择距离生成树最 近的顶点。方法是遍历数组 L,找出length不等于0,且 为最小的距离。 length等于0表示当前顶点已 经被选入生成树。

6L: u v a a a a a a le

ngth 0 6 1 5

a 1 5 6 5 c 4 6

5 d 2 f

b 3 e

1 2 3 4 5 6

a b c d e f

∞ ∞

c被选中，加入生成树中。 并更新数组L。

6L: u v a a a a a a length 0 6 0 5

a 1 5 6 5 c 4 6

5 d 2 f

b 3 e

1 2 3 4 5 6

a b c d e f

∞ ∞

更新数组L,c被选入生成树， 故对应项的Length应该赋值 为0

6L: u a b c d e f v a a a a a a length 0 6

a 1 5 6 5 c 4 6

5 d 2 f

b 3 e

1 2 3 4 5 6

0 5

更新剩余顶点到当前生成树的最短距离。

∞ ∞

以顶点b为例。c加入生成树前，b到生成树的 最短距离已经在数组L中保存，c加入后，比 较L中数据和边(b,c)的权值，如果后者小， 说明b到生成树的距离变小了，应该更新，否 则不变。

6L: u v a a a a a a length 0 6 0 5

a 1 5 6 5 c 4 6

5 d 2 f

b 3 e

1 2 3 4 5 6

a b c d e f

∞ ∞ba=6<bc=5,故更新

6L: u v a c a a a a length 0 5 0 5

a 1 5 6 5 c 4 6

5 d 2 f

b 3 e

1 2 3 4 5 6

a b c d e f

∞ ∞

L:

u

v a c a a a a

length 0 5 0 5

6 b 3 e 5 6

a 1 5 c 4 6

5 d 2 f

1 2 3 4 5 6

a b c d e f

∞ ∞da=5=dc=5,故不变

6L: u v a c a a a a length 0 5 0 5

a 1 5 6 5 c 4 6

5 d 2 f

b 3 e

1 2 3 4 5 6

a b c d e f

∞ ∞

ea= ∞ >ec=6,故更新