第 8 章 图
{ 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)
以顶点①为根的深度优先生成树: