7.3.3 深度优先生成树和广度优先生成树 　　由于生成森林中的边是在遍历过程中产生的，因此得到生成森林的算法只要对遍历的算法略加修改即可，即将对顶点的访问改为"在生成树上插入结点"即可。以下是生成深度优先森林的算法。 算法 7.6 　　void DFSForest(Graph G, CSTree &T) 　{ 　　// 建立无向图 G 的深度优先生成森林的(最左)孩子 　　// (右)兄弟链表，T 为孩子-兄弟链表的根指针 　　T = NULL; 　　for (v=0; v<G.vexnum; ++v) visited[v] = FALSE; 　　for (v=0; v<G.vexnum; ++v)
	if (!visited[v]) { 　　　　　　　　// 第v顶点为新的生成树的根结点 　　　　p = new CSNode;　　　　　　　　　// 分配根结点 　　　　if (!p) exit(1); 　　　　　　　　// 存储分配失败 　　　　p->data = GetVex(G,v); 　　　　　 // 给该结点赋值 　　　　p->firstchild = p->nextsibling = NULL; 　　　　if (!T) T = p; 　　　　　　　　　// 是第一棵生成树的根(T的根) 　　　　else q->nextsibling = p;// 是其它生成树的根(前一棵的根的"兄弟") 　　　　q = p; 　　　　　　　　　　　　　// q 指示当前生成树的根 　　　　DFSTree(G,v,p);　　　　　　　　　// 建立以 p 为根的生成树 　　　} // if 　} // DFSForest 算法 7.7 　　void DFSTree(Graph G, int v, CSTree &T) 　{ 　　// 从第 v 个顶点出发深度优先遍历图 G，建立以 T 为根的生成树 　　visited[v] = TRUE; first =TRUE; 　　for (w=FisrtAdjVex(G,v); w; w=NextAdjVex(G,v,w)) 　　　if (!visited[w]) { 　　　　p = new CSNode; 　　　　　　　　　　// 分配孩子结点 　　　　if (!p) exit(1); 　　　　　　　　　　// 存储分配失败 　　　　p->data = GetVex(G,w); 　　　　p->firstchild = p->nextsibling = NULL; 　　　　if (first) { 　　　　　　// w 是 v 的第一个未被访问的邻接顶点 　　　　　T->firstchild = p; first = FALSE;　// 是根的左孩子结点 　　　　} // if 　　　　else {　　　　　　　　　// w 是 v 的其它未被访问的邻接顶点 　　　　　q->nextsibling = p; 　　// 是上一邻接顶点的右兄弟结点 　　　　} // else 　　　　q = p; 　　　　DFSTree(G,w,q);// 从第 w 个顶点出发深度优先遍历图G,建立以 q 为根的子树 　　　} // if 　} // DFSTree 　　类似地修改算法7.5便可得到构造广度优先生成森林的算法。显然，无论是深度优先森林或广度优先森林，算法的时间复杂度和遍历算法的时间复杂度相同。		访问顶点 v，将 DFS 中访问出发顶点的操作提前到此。