第8章图 if( Edge00>0)i e head=i; e tail =j;ecost=Edge[0]; ap Insert(e )i while( count< Vertices Num )i heap. RemoveMin(e); i=set. Find (e. head ) j=set. Find( e. tail ) if(il=j)t set Union(1j); cout<<"("<<ehead <<","<<e tail <<", "< ecost <<")<<endl; 8-14利用 Dijkstra算法的思想,设计一个求最小生成树的算法。 【解答】 计算连通网络的最小生成树的 Dijkstra算法可描述如下:将连通网络中所有的边以方便的次序逐步 加入到初始为空的生成树的边集合T中。每次选择并加入一条边时,需要判断它是否会与先前加入T的 边构成回路。如果构成了回路,则从这个回路中将权值最大的边退选 下面以邻接矩阵作为连通网络的存储表示,并以并查集作为判断是否出现回路的工具,分析算法的 执行过程。 ①②③④⑤⑥ ① 06 01811 026⑤ 并查集,表明4 个结点在同 ④⑥ 连通分量上第 8 章 图 105 if ( Edge[i][j] > 0 ) { e.head = i; e.tail = j; e.cost = Edge[i][j]; heap.Insert ( e ); } count = 1; while ( count < VerticesNum ) { heap.RemoveMin ( e ); i = set.Find ( e.head ); j = set.Find ( e.tail ); if ( i != j ) { set.Union ( i, j ); count++; cout << "( " << e.head << ", " << e.tail << ", " << e.cost << " )" << endl; } } } 8-14 利用 Dijkstra 算法的思想，设计一个求最小生成树的算法。 【解答】 计算连通网络的最小生成树的 Dijkstra 算法可描述如下：将连通网络中所有的边以方便的次序逐步 加入到初始为空的生成树的边集合 T 中。每次选择并加入一条边时，需要判断它是否会与先前加入 T 的 边构成回路。如果构成了回路，则从这个回路中将权值最大的边退选。 下面以邻接矩阵作为连通网络的存储表示，并以并查集作为判断是否出现回路的工具，分析算法的 执行过程。 ① ② ⑤ ④ ⑥ ③ 18 14 16 26 21 19 11 9 5 6                     − − − − − − − − − − − − − −   −    = 0 0 26 0 18 11 0 6 0 5 9 19 0 16 14 21 Edge ① ② ③ ④ ⑤ ⑥ ① ② ③ ④ ⑤ ⑥ ① ② ⑤ ④ 14 ⑥ ③ 16 21 ① ② ⑤ ⑥ 并查集, 表明 4 个结点在同一 连通分量上 ① ② ⑤ ④ 14 ⑥ ③ 16 21 ① ② ⑤ ⑥ 19 9 5  ③ ④ ① ② ⑤ ④ 14 ⑥ ③ 16 ① ② ⑤ ⑥ 5 ③ ④ 19 9 6  ① ② ⑤ ④ 14 ⑥ ③ 16 ① ② ⑤ ⑥ 5 ③ 6 ④ 19 11 