第8章图 第8章图 8-1画出1个顶点、2个顶点、3个顶点、4个顶点和5个顶点的无向完全图。试证明在n个顶点的无向 完全图中,边的条数为n(n-1)2。 【解答】 1个顶点的2个顶点的 无向完全图无向完全图 3个顶点的 4个顶点的 无向完全图 无向完全图 5个顶点的 无向完全图 【证明】 在有n个顶点的无向完全图中,每一个顶点都有一条边与其它某一顶点相连,所以每一个顶点有n-1 条边与其他n-1个顶点相连,总计n个顶点有n(n-1)条边。但在无向图中,顶点i到顶点j与顶点j到顶 点i是同一条边,所以总共有n(n-1)2条边 8-2右边的有向图是强连通的吗?请列出所有的简单路径。 【解答】 判断一个有向图是否强连通,要看从任一顶点出发是否能够回到该顶 点。右面的有向图做不到这一点,它不是强连通的有向图。各个顶点自成 强连通分量 所谓简单路径是指该路径上没有重复的顶点 从顶点A出发,到其他的各个顶点的简单路径有A→B,A→D→B,A→B→C,A→D→B→C,A D,A→B→E,A→D→E,A→D→B→E,A→B→C→F→E,A→D→B→C→F→E,A→B→C→F,A →D→B→C→F。 从顶点B出发,到其他各个顶点的简单路径有B→C,B→C→F,B→E,B→C→F→E 从顶点C出发,到其他各个顶点的简单路径有C→F,C→F→E 从顶点D出发,到其他各个顶点的简单路径有D→B,D→B→C,D→B→C→F,D→E,D→B→E D→B→C→F→E 从顶点E出发,到其他各个顶点的简单路径无 从顶点F出发,到其他各个顶点的简单路径有F→E。 8-3给出右图的邻接矩阵、邻接表和邻接多重表表示 【解答】 (1)邻接矩阵 010100 0010 0 000001 Edge=0 100 000000 000010
第 8 章 图 96 = 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 0 1 0 0 1 0 1 0 0 Edge 第 8 章 图 8-1 画出 1 个顶点、2 个顶点、3 个顶点、4 个顶点和 5 个顶点的无向完全图。试证明在 n 个顶点的无向 完全图中，边的条数为 n(n-1)/2。 【解答】 【证明】 在有 n 个顶点的无向完全图中，每一个顶点都有一条边与其它某一顶点相连，所以每一个顶点有 n-1 条边与其他 n-1 个顶点相连，总计 n 个顶点有 n(n-1)条边。但在无向图中，顶点 i 到顶点 j 与顶点 j 到顶 点 i 是同一条边，所以总共有 n(n-1)/2 条边。 8-2 右边的有向图是强连通的吗？请列出所有的简单路径。 【解答】 判断一个有向图是否强连通，要看从任一顶点出发是否能够回到该顶 点。右面的有向图做不到这一点，它不是强连通的有向图。各个顶点自成 强连通分量。 所谓简单路径是指该路径上没有重复的顶点。 从顶点 A 出发，到其他的各个顶点的简单路径有 A→B，A→D→B，A→B→C，A→D→B→C，A →D，A→B→E，A→D→E，A→D→B→E，A→B→C→F→E，A→D→B→C→F→E，A→B→C→F，A →D→B→C→F。 从顶点 B 出发，到其他各个顶点的简单路径有 B→C，B→C→F，B→E，B→C→F→E。 从顶点 C 出发，到其他各个顶点的简单路径有 C→F，C→F→E。 从顶点 D 出发，到其他各个顶点的简单路径有 D→B，D→B→C，D→B→C→F，D→E，D→B→E， D→B→C→F→E。 从顶点 E 出发，到其他各个顶点的简单路径无。 从顶点 F 出发，到其他各个顶点的简单路径有 F→E。 8-3 给出右图的邻接矩阵、邻接表和邻接多重表表示。 【解答】 (1) 邻接矩阵 1 个顶点的 无向完全图 2 个顶点的 无向完全图 3 个顶点的 无向完全图 4 个顶点的 无向完全图 5 个顶点的 无向完全图 A B C D E F A B C D E F
第8章图 (2)邻接表 (出边表 5∧ 3D (入边表) 1 B -3B (3)邻接多重表(十字链表) data fin fout ij ilink jlink 0A∧ 0 03∧∧ 4121(((((B.C) 2|5A 31 54A∧cE 8-4用邻接矩阵表示图时,若图中有1000个顶点,1000条边,则形成的邻接矩阵有多少矩阵元素?有 多少非零元素?是否稀疏矩阵? 【解答】 个图中有1000个顶点,其邻接矩阵中的矩阵元素有10002=1000000个。它有1000个非零元素(对 于有向图)或2000个非零元素(对于无向图),因此是稀疏矩阵。 8-5用邻接矩阵表示图时,矩阵元素的个数与顶点个数是否相关?与边的条数是否相关? 【解答】 用邻接矩阵表示图,矩阵元素的个数是顶点个数的平方,与边的条数无关。矩阵中非零元素的个数 与边的条数有关 8-6有n个顶点的无向连通图至少有多少条边?有n个顶点的有向强连通图至少有多少条边?试举例说 【解答】
第 8 章 图 97 (2) 邻接表 (3) 邻接多重表（十字链表） 8-4 用邻接矩阵表示图时，若图中有 1000 个顶点，1000 条边，则形成的邻接矩阵有多少矩阵元素？有 多少非零元素？是否稀疏矩阵？ 【解答】 一个图中有 1000 个顶点，其邻接矩阵中的矩阵元素有 10002 = 1000000 个。它有 1000 个非零元素（对 于有向图）或 2000 个非零元素（对于无向图），因此是稀疏矩阵。 8-5 用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否相关？ 【解答】 用邻接矩阵表示图，矩阵元素的个数是顶点个数的平方，与边的条数无关。矩阵中非零元素的个数 与边的条数有关。 8-6 有 n 个顶点的无向连通图至少有多少条边？有 n 个顶点的有向强连通图至少有多少条边？试举例说 明。 【解答】 0 A 1 B 2 C 3 D 4 E 5 F 1 0 A 1 B 2 C 3 D 4 E 5 F 3 2 4 5 1 4 4 0 3 1 0 1 3 5 2 ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ （出边表） （入边表） 0 A 1 B 2 C 3 D 4 E 5 F data fin fout i j ilink jlink 0 1 (A, B) 0 3 (A, D) 1 2 (B, C) 1 4 (B, E) 2 5 (C, F) 3 1 (D, B) 3 4 (D, E) 5 4 (F, E) ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧
第8章图 n个顶点的无向连通图至少有n-1条边,n个顶点的有向强连通图至少有n条边。例如 无向图 ① 有向图① 特例情况是当n=1时,此时至少有0条边 8-7对于有n个顶点的无向图,采用邻接矩阵表示,如何判断以下问题:图中有多少条边?任意两个顶 点i和j之间是否有边相连?任意一个顶点的度是多少? 【解答】 用邻接矩阵表示无向图时,因为是对称矩阵,对矩阵的上三角部分或下三角部分检测一遍,统计其 中的非零元素个数,就是图中的边数。如果邻接矩阵中A[[不为零,说明顶点i与顶点j之间有边相 连。此外统计矩阵第i行或第i列的非零元素个数,就可得到顶点i的度数 8-8对于如右图所示的有向图,试写出: (1)从顶点①出发进行深度优先搜索所得到的深度优先生成树 (2)从顶点②出发进行广度优先搜索所得到的广度优先生成树 【解答】 (1)以顶点①为根的深度优先生成树(不唯一):②③④⑤⑥ (2)以顶点②为根的广度优先生成树 8-9试扩充深度优先搜索算法,在遍历图的过程中建立生成森林的左子女-右兄弟链表。算法的首部为 void Graph:DFS( const int v, int visited[ I TreeNode*t)其中,指针t指向生成森林上具有图 顶点ⅴ信息的根结点。(提示:在继续按深度方向从根ⅴ的某一未访问过的邻接顶点w向下遍历之前, 建立子女结点。但需要判断是作为根的第一个子女还是作为其子女的右兄弟链入生成树。) 【解答】 为建立生成森林,需要先给出建立生成树的算法,然后再在遍历图的过程中,通过一次次地调用这 个算法,以建立生成森林 te plate void Graph: DFS Tree( const int v, int visited [ TreeNode*t)4 ∥从图的顶点v出发,深度优先遍历图,建立以t(已在上层算法中建立)为根的生成树 int w=Get FirstNeighbor(v); 取第一个邻接顶点 hile(wI=-l)i ∥若邻接顶点存在
第 8 章 图 98 ① ② ③ ④ ⑤ 或 ① ② ③ ④ ⑤ ① ② ③ ④ ⑤ ① ② ③ ④ ⑤ n 个顶点的无向连通图至少有 n-1 条边，n 个顶点的有向强连通图至少有 n 条边。例如： 特例情况是当 n = 1 时，此时至少有 0 条边。 8-7 对于有 n 个顶点的无向图，采用邻接矩阵表示，如何判断以下问题： 图中有多少条边？任意两个顶 点 i 和 j 之间是否有边相连？任意一个顶点的度是多少？ 【解答】 用邻接矩阵表示无向图时，因为是对称矩阵，对矩阵的上三角部分或下三角部分检测一遍，统计其 中的非零元素个数，就是图中的边数。如果邻接矩阵中 A[i][j] 不为零，说明顶点 i 与顶点 j 之间有边相 连。此外统计矩阵第 i 行或第 i 列的非零元素个数，就可得到顶点 i 的度数。 8-8 对于如右图所示的有向图，试写出： (1) 从顶点①出发进行深度优先搜索所得到的深度优先生成树； (2) 从顶点②出发进行广度优先搜索所得到的广度优先生成树； 【解答】 (1) 以顶点①为根的深度优先生成树（不唯一）：② ③ ④ ⑤ ⑥ (2) 以顶点②为根的广度优先生成树： 8-9 试扩充深度优先搜索算法，在遍历图的过程中建立生成森林的左子女-右兄弟链表。算法的首部为 void Graph::DFS ( const int v, int visited [ ], TreeNode * t ) 其中，指针 t 指向生成森林上具有图 顶点 v 信息的根结点。（提示：在继续按深度方向从根 v 的某一未访问过的邻接顶点 w 向下遍历之前， 建立子女结点。但需要判断是作为根的第一个子女还是作为其子女的右兄弟链入生成树。） 【解答】 为建立生成森林，需要先给出建立生成树的算法，然后再在遍历图的过程中，通过一次次地调用这 个算法，以建立生成森林。 te mplate void Graph :: DFS_Tree ( const int v, int visited [ ], TreeNode *t ) { //从图的顶点 v 出发, 深度优先遍历图, 建立以 t (已在上层算法中建立)为根的生成树。 Visited[v] = 1; int first = 1; TreeNode * p, * q; int w = GetFirstNeighbor ( v ); //取第一个邻接顶点 while ( w != -1 ) { //若邻接顶点存在
if vositedw]=0)i 且该邻接结点未访问过 p= new TreeNode( Get Value(w)); 建立新的生成树结点 if first==1) l若根还未链入任一子女 新结点p成为根*的第一个子女 else q->setNextSibling(p ); ∥否则新结点*p成为q的下一个兄弟 指针q总指示兄弟链最后一个结点 DFS Tree( w, visited, q); 从*q向下建立子树 w=GetNextNeighbor (V, w); ∥取顶点v排在邻接顶点w的下一个邻接顶点 下一个算法用于建立以左子女右兄弟链表为存储表示的生成森林 template void Graph: DFS Forest( Tree&T) ∥从图的顶点ⅴ出发,深度优先遍历图,建立以左子女右兄弟链表表示的生成森林T。 Troot= NULL; int n= NumberOfVertices ( ∥顶点个数 TreeNode*p,'g: int"visited new int [n ∥建立访问标记数组 for( int v=0; VsetNextSibling(p); 否则新结点*p成为q的下一个兄弟 DFS Tree(v, visited, p ); 健建立以*p为根的生成树 8-10用邻接表表示图时,顶点个数设为n,边的条数设为e,在邻接表上执行有关图的遍历操作时,时 间代价是O(n+e)?还是O(n+e)?或者是O(max(n,e)? 【解答】 在邻接表上执行图的遍历操作时,需要对邻接表中所有的边链表中的结点访问一次,还需要对所有 的顶点访问一次,所以时间代价是On+e)。 8-11右图是一个连通图,请画出 (1)以顶点①为根的深度优先生成树 (2)如果有关节点,请找出所有的关节点 (3)如果想把该连通图变成重连通图,至少在图中加几条边? 如何加? 【解答】 (1)以顶点①为根的深度优先生成树:
第 8 章 图 99 if ( vosited[w] == 0 ) { //且该邻接结点未访问过 p = new TreeNode ( GetValue (w) ); //建立新的生成树结点 if ( first == 1 ) //若根*t 还未链入任一子女 { t->setFirstChild ( p ); first = 0; } //新结点*p 成为根*t 的第一个子女 else q->setNextSibling ( p ); //否则新结点*p 成为*q 的下一个兄弟 q = p; //指针 q 总指示兄弟链最后一个结点 DFS_Tree ( w, visited, q ); //从*q 向下建立子树 } w = GetNextNeighbor ( v, w ); //取顶点 v 排在邻接顶点 w 的下一个邻接顶点 } } 下一个算法用于建立以左子女-右兄弟链表为存储表示的生成森林。 template void Graph :: DFS_Forest ( Tree & T ) { //从图的顶点 v 出发, 深度优先遍历图, 建立以左子女-右兄弟链表表示的生成森林 T。 T.root = NULL; int n = NumberOfVertices ( ); //顶点个数 TreeNode * p, * q; int * visited = new int [ n ]; //建立访问标记数组 for ( int v = 0; v ( GetValue ( v ) ); //建立新结点*p if ( T.root == NULL ) T.root = p; //原来是空的生成森林, 新结点成为根 else q-> setNextSibling ( p ); //否则新结点*p 成为*q 的下一个兄弟 q = p; DFS_Tree ( v, visited, p ); //建立以*p 为根的生成树 } } 8-10 用邻接表表示图时，顶点个数设为 n，边的条数设为 e，在邻接表上执行有关图的遍历操作时，时 间代价是 O(n*e)？还是 O(n+e)？或者是 O(max(n,e))？ 【解答】 在邻接表上执行图的遍历操作时，需要对邻接表中所有的边链表中的结点访问一次，还需要对所有 的顶点访问一次，所以时间代价是 O(n+e)。 8-11 右图是一个连通图，请画出 (1) 以顶点①为根的深度优先生成树； (2) 如果有关节点，请找出所有的关节点。 (3) 如果想把该连通图变成重连通图，至少在图中加几条边？ 如何加？ 【解答】 (1) 以顶点①为根的深度优先生成树： ⑩ ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ⑨
第8章图 (2)关节点为①,②,③,⑦,⑧ 3)至少加四条边(1,10),(3,4,(4,5)(5,6)。从③的子孙结点⑩到③的祖先结点①引一条边,从② 的子孙结点④到根①的另一分支③引一条边,并将⑦的子孙结点⑤、⑥与结点④连结起来,可使其变为 重连通图 12试证明在一个有n个顶点的完全图中,生成树的数目至少有2n1-1 【证明】略 8-13编写一个完整的程序,首先定义堆和并查集的结构类型和 相关操作,再定义 Kruskal求连通网络的最小生成树算法的实 现,并以右图为例,写出求解过程中堆、并查集和最小生成树79 的变化 【解答】 求解过程的第一步是对所有的边,按其权值大小建堆: 口27 345 山应d[24 2区3ld 加(1,2),(1,3), (2,3) 加(2,4) 加(3,4) B山区4]2lo 邮B山区4p区23B68 加(3,5) 加(3,6) b4230国6]加6) 3山
第 8 章 图 100 (2) 关节点为 ①,②,③,⑦,⑧ (3) 至少加四条边 (1, 10), (3, 4), (4, 5), (5, 6)。从③的子孙结点⑩到③的祖先结点①引一条边，从② 的子孙结点④到根①的另一分支③引一条边，并将⑦的子孙结点⑤、⑥与结点④连结起来，可使其变为 重连通图。 8-12 试证明在一个有 n 个顶点的完全图中，生成树的数目至少有 2 n-1-1。 【证明】略 8-13 编写一个完整的程序，首先定义堆和并查集的结构类型和 相关操作，再定义 Kruskal 求连通网络的最小生成树算法的实 现。并以右图为例，写出求解过程中堆、并查集和最小生成树 的变化。 【解答】 求解过程的第一步是对所有的边，按其权值大小建堆： 1 3 11 ① ② ③ ④ ⑤ ⑥ 11 7 6 8 5 10 9 7 ⑩ ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ⑨ ⑩ ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ⑨ 1 2 7 1 3 11 2 3 10 1 2 7 2 4 9 2 3 10 1 3 11 3 4 5 1 2 7 2 3 10 2 4 9 加(1, 2), (1, 3), (2,3) 加(2, 4) 加(3, 4) 1 3 11 3 4 5 1 2 7 3 5 7 2 4 9 2 3 10 1 3 11 3 4 5 1 2 7 3 5 7 2 4 9 2 3 10 3 6 8 加(3, 5) 加(3, 6) 1 2 7 3 4 5 5 6 6 3 5 7 2 4 9 2 3 10 3 6 8 1 3 11 加(5, 6)
第8章图 求解过程中并查集与堆的变化 ④⑥ 选(345)国山国4[238]560面国4 ④⑥ D② 23 选(2,)[B3山[249 选(357⑥3山 ②④⑤ 21310 ①④ 山 ⑥选(3.6.)在同一连通分量上,不加②⑥选(249,结束 最后得到的生成树如下 6 并查集的存储表示 完整的程序如下 #include class MinHeap i num MaxHeapsize=503: MinHeap( int Maxsize MaxHeap Size ) MinHeap( type array[, int n ) void Insert( const Type &ele ) void RemoveMin( Type &Min ) void Output O private void Filter Down( int start, int end ) void FilterUp( int end )i Type "pl int Currentsize; class UFSets i
第 8 章 图 101 求解过程中并查集与堆的变化： 最后得到的生成树如下 完整的程序如下: #include template class MinHeap { public: enum { MaxHeapSize = 50 }; MinHeap ( int Maxsize = MaxHeapSize ); MinHeap ( Type Array[ ], int n ); void Insert ( const Type &ele ); void RemoveMin ( Type &Min ); void Output (); private: void FilterDown ( int start, int end ); void FilterUp ( int end ); Type *pHeap; int HMaxSize; int CurrentSize; }; class UFSets { public: 3 1 -6 3 3 5 1 3 11 3 5 7 2 4 9 3 6 8 2 3 10 ① ② ③ ④ ⑤ ⑥ 6 7 7 5 9 ③ ④ 1 3 11 5 6 6 1 2 7 3 5 7 选(3,4,5) 2 4 9 2 3 10 3 6 8 ③ ④ ⑤ ⑥ 选(5,6,6) 1 3 11 1 2 7 3 5 7 2 4 9 2 3 10 3 6 8 ③ ④ ⑤ ⑥ 选(1,2,7) ① ② ③ ④ ⑤ 选(3,5,7) ⑥ ① ② 1 3 11 2 4 9 2 3 10 3 6 8 ③ ④ ⑤ ⑥ 选(3,6,8), 在同一连通分量上, 不加 ① ② 1 3 11 2 3 10 2 4 9 ③ ④ ⑤ ⑥ 选(2,4,9), 结束 ① ② 1 3 11 2 3 10 0 1 2 3 4 5 6 并查集的存储表示
第8章图 i MaxUnionSize =503; lionIze ) FSetso delete []m pArent; 3 void Union( int Rootl, int Root ) int Find( int x ) r at m sIze: 中 m pArent 50}; Graph( int Vertices=0)( Current Vertices = Vertices; InitGraph0: 1 void InitGraph 0; int Get Vertices(i return Current Vertices; 3 private int Current Vertices class GraphEdge i head, tail &ed); GraphEdge : operator cost <=ed cos UFSets: UFSets( int MaxSize)i m_pArent=new int[m sIze] void UFSets: Union( int Rootl, int Root2 )t
第 8 章 图 102 enum { MaxUnionSize = 50 }; UFSets ( int MaxSize = MaxUnionSize ); ~UFSets () { delete [ ] m_pParent; } void Union ( int Root1, int Root2 ); int Find ( int x ); private: int m_iSize; int *m_pParent; }; class Graph { public: enum { MaxVerticesNum = 50 }; Graph( int Vertices = 0) { CurrentVertices = Vertices; InitGraph(); } void InitGraph (); void Kruskal (); int GetVerticesNum () { return CurrentVertices; } private: int Edge[MaxVerticesNum][MaxVerticesNum]; int CurrentVertices; }; class GraphEdge { public: int head, tail; int cost; int operator cost <= ed.cost; } UFSets :: UFSets ( int MaxSize ) { m_iSize = MaxSize; m_pParent = new int[m_iSize]; for ( int i = 0; i < m_iSize; i++ ) m_pParent[i] = -1; } void UFSets :: Union ( int Root1, int Root2 ) { m_pParent[Root2] = Root1; }
第8章图 int UFSets: Find( intx)( while( m pParentx >=0)x=m pArent(x template MinHeap:: MinHeap( int Maxsize )i HMaxS ize maxsize pHeap= new Type[HMaxSize]: template MinHeap: MinHeap( Type Array[, int n)i HMaxsize=( n=0)4 FilterDown(IPos, Currentsize ) template void MinHeap:: Filter Down( int start, int end)t int i=star,j=2 start +1; if(j void MinHeap: FilterUp( int end)i int i=end, j=( end-1)/2; while(1>0)( if( pHeap[ <= Temp)break pHeap(=pHeapD: i=j;j=(j-1)/2;
第 8 章 图 103 int UFSets :: Find ( int x ) { while ( m_pParent[x] >= 0 ) x = m_pParent[x]; return x; } template MinHeap :: MinHeap ( int Maxsize ) { HMaxSize = Maxsize; pHeap = new Type[HMaxSize]; CurrentSize = -1; } template MinHeap :: MinHeap ( Type Array[], int n ) { HMaxSize = ( n = 0 ) { FilterDown ( iPos, CurrentSize ); iPos--; } } template void MinHeap :: FilterDown ( int start, int end ) { int i = start, j = 2 * start + 1; Type Temp = pHeap[i]; while ( j void MinHeap :: FilterUp ( int end ) { int i = end, j = ( end - 1 ) / 2; Type Temp = pHeap[i]; while ( i > 0 ) { if ( pHeap[j] <= Temp ) break; pHeap[i] = pHeap[j]; i = j; j = ( j - 1 ) / 2; }
第8章图 pHeap[=Temp; template void MinHeapType>: Insert const Type &ele SIZe++: if( Currents HMaxSize )return; FilterUp( CurrentSize ) template void MinHeap: RemoveMin( Type &Min)( Min= pHeap[0; pHeap[o]=pHeap[CurrentSize]: Filter Down(0, CurrentSize ) template void MinHeap: Output(( for ( int 1=0; i heap( Vertices Num *Vertices Num ) UFSets set( VerticesNum ) for(j=i+1:j< VerticesNum; j++)
第 8 章 图 104 pHeap[i] = Temp; } template void MinHeap :: Insert ( const Type &ele ) { CurrentSize++; if ( CurrentSize == HMaxSize ) return; pHeap[CurrentSize] = ele; FilterUp ( CurrentSize ); } template void MinHeap :: RemoveMin ( Type &Min ) { if ( CurrentSize void MinHeap :: Output ( ) { for ( int i = 0; i heap ( VerticesNum *VerticesNum ); UFSets set ( VerticesNum ); for ( i = 0; i < VerticesNum; i++ ) for ( j = i + 1; j < VerticesNum; j++ )
第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 ) set Union(1j); cout<<"("<<ehead <<","<<e tail <<", "< ecost <<")<<endl; 8-14利用 Dijkstra算法的思想,设计一个求最小生成树的算法。 【解答】 计算连通网络的最小生成树的 Dijkstra算法可描述如下:将连通网络中所有的边以方便的次序逐步 加入到初始为空的生成树的边集合T中。每次选择并加入一条边时,需要判断它是否会与先前加入T的 边构成回路。如果构成了回路,则从这个回路中将权值最大的边退选 下面以邻接矩阵作为连通网络的存储表示,并以并查集作为判断是否出现回路的工具,分析算法的 执行过程。 ①②③④⑤⑥ 016∞∞1421 ① 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