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) 以顶点①为根的深度优先生成树： ⑩ ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ⑨