第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 ) { //若邻接顶点存在