8-9试扩充深度优先搜索算法,在遍历图的过程中建立生成森林的左子女-右兄弟链表 算法的首部为 viod Graph:DFS( const int y, int visited[l, Tree Node<int>*t)其中,指 针t指向生成森林上具有图顶点ν信息的根结点。(提示:在继续按深度方向从根ν的某 一未访问过的邻接顶点w向下遍历之前,建立子女结点。但需要判断是作为根的第一个 子女还是作为其子女的右兄弟链入生成树。) 8-10用邻接表表示图时,顶点个数设为n,边的条数设为e,在邻接表上执行有关图的 遍历操作时,时间代价是On*e)?还是O(n+e)?或者是Omax(n,e) 【解答】在邻接表上执行图的遍历操作时,需要对邻接表中所有的边链表中的结点访问 次,还需要对所有的顶点访问一次,所以时间代价是O(n+e)。 8-15右图是一个连通图,请画出 ②2 (1)以顶点①为根的深度优先生成树 (2)如果有关节点,请找出所有的关节点。 (3)如果想把该连通图变成重连通图,至少在 图中加几条边?如何加? 【解答】 (1)从顶点①出发的深度优先生成树为 ③人 此答案不唯 8 8-16试证明在一个有n个顶点的完全图中,生成 树的数目至少有2n1-1 10 8-17编写一个完整的程序,首先定义堆和并查集 的结构类型和相关操作,再定义 Kruskal求连通 网络的最小生成树算法的实现。并以右图为例,8-9 试扩充深度优先搜索算法，在遍历图的过程中建立生成森林的左子女-右兄弟链表。 算法的首部为viod Graph::DFS ( const int v, int visited [ ], TreeNode<int> * t ) 其中，指 针 t 指向生成森林上具有图顶点 v 信息的根结点。（提示：在继续按深度方向从根 v 的某 一未访问过的邻接顶点 w 向下遍历之前，建立子女结点。但需要判断是作为根的第一个 子女还是作为其子女的右兄弟链入生成树。） 8-10 用邻接表表示图时，顶点个数设为 n，边的条数设为 e，在邻接表上执行有关图的 遍历操作时，时间代价是 O(n*e)？还是 O(n+e)？或者是 O(max(n,e))？ 【解答】在邻接表上执行图的遍历操作时，需要对邻接表中所有的边链表中的结点访问 一次，还需要对所有的顶点访问一次，所以时间代价是 O(n+e)。 8-15 右图是一个连通图，请画出 (1) 以顶点①为根的深度优先生成树； (2) 如果有关节点，请找出所有的关节点。 (3) 如果想把该连通图变成重连通图，至少在 图中加几条边？如何加？ 【解答】 (1) 从顶点①出发的深度优先生成树为 此答案不唯一 (2) 8-16 试证明在一个有 n 个顶点的完全图中，生成 树的数目至少有 2 n-1 -1。 8-17 编写一个完整的程序，首先定义堆和并查集 的结构类型和相关操作，再定义 Kruskal 求连通 网络的最小生成树算法的实现。并以右图为例