第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 Ed 0100 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<int>*t)其中,指针t指向生成森林上具有图 顶点ⅴ信息的根结点。(提示:在继续按深度方向从根ⅴ的某一未访问过的邻接顶点w向下遍历之前, 建立子女结点。但需要判断是作为根的第一个子女还是作为其子女的右兄弟链入生成树。) 【解答】 为建立生成森林,需要先给出建立生成树的算法,然后再在遍历图的过程中,通过一次次地调用这 个算法,以建立生成森林 te plate<Type> void Graph<Type>: DFS Tree( const int v, int visited [ TreeNode<Type>*t)4 ∥从图的顶点v出发,深度优先遍历图,建立以t(已在上层算法中建立)为根的生成树 Visited v]=1: int first=1; TreeNode<Type>*p,*q; int w=Get FirstNeighbor(v); 取第一个邻接顶点 w|=-1){ ∥若邻接顶点存在
第 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<int> * t ) 其中，指针 t 指向生成森林上具有图 顶点 v 信息的根结点。（提示：在继续按深度方向从根 v 的某一未访问过的邻接顶点 w 向下遍历之前， 建立子女结点。但需要判断是作为根的第一个子女还是作为其子女的右兄弟链入生成树。） 【解答】 为建立生成森林，需要先给出建立生成树的算法，然后再在遍历图的过程中，通过一次次地调用这 个算法，以建立生成森林。 te mplate<Type> void Graph<Type> :: DFS_Tree ( const int v, int visited [ ], TreeNode<Type> *t ) { //从图的顶点 v 出发, 深度优先遍历图, 建立以 t (已在上层算法中建立)为根的生成树。 Visited[v] = 1; int first = 1; TreeNode<Type> * p, * q; int w = GetFirstNeighbor ( v ); //取第一个邻接顶点 while ( w != -1 ) { //若邻接顶点存在
if vositedw]=0)i 且该邻接结点未访问过 p= new TreeNode<Type>( 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<Type> void Graph<Type>: DFS Forest( Tree<Type>&T) ∥从图的顶点ⅴ出发,深度优先遍历图,建立以左子女右兄弟链表表示的生成森林T。 Troot= NULL; int n= NumberOfVertices ( ∥顶点个数 TreeNode<Type>*p,'g: int"visited new int [n ∥建立访问标记数组 for( int v=0; V<n; v++)visited v=0; v<n;v++) 逐个顶点检测 if( visited=0)i ∥若尚未访问过 p=new Tr anOde<Iype( Get Value(v);建立新结点p if( Troot ==NULL )Troot =p ∥原来是空的生成森林,新结点成为根 else q->setNextSibling(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<Type> ( 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<Type> void Graph<Type> :: DFS_Forest ( Tree<Type> & T ) { //从图的顶点 v 出发, 深度优先遍历图, 建立以左子女-右兄弟链表表示的生成森林 T。 T.root = NULL; int n = NumberOfVertices ( ); //顶点个数 TreeNode<Type> * p, * q; int * visited = new int [ n ]; //建立访问标记数组 for ( int v = 0; v < n; v++ ) visited[v] = 0; for ( v = 0; v < n; v++ ) //逐个顶点检测 if ( visited[v] == 0 ) { //若尚未访问过 p = new TreeNode<Type> ( 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)