7.4.1无向图的连通分量和生成树
7.4.1无向图的连通分量和生成树。
void DFSForest(Graph G,CSTree &T)
//建立无向图G 的深度优先生成森林的
//（最左）孩子（右）兄弟链表T 。
{
T=NULL;
for(v=0;v
visited[v]=FALSE;
for(v=0;v
{
if(!visited[v]) //第v 顶点为新的生成树的根节点。 {
p=(CSTree)malloc(sizeof(CSNode)); //分配根节点。
*p={GetVex(G,v),NULL,NULL}; //给该节点赋值。
if(!T) T=p; //是第一棵生成树的根（T 的根）。
else q->nextSibling=p; //是其他生成树的根（前一棵的根的“兄弟”）。 q=p; //q指示当前生成树的根。
DFSTree(G,v,p); //建立以p 为根的生成树。
}// if(!visited[v])
}// for(v=0;v
}// DFSForest
Void DFSTree(Graph G,int v,CSTree &T)
//从第v 个顶点出发深度优先遍历图G ，建立以T 为根的生成树。
{
visited[v]=TRUE;first=TRUE;
for(w=FirstAdjVex(G,v);w;w=NextAdjVex(G,v,w))
{
if(!visited[w])
{
p=(CSTree)malloc(sizeof(CSNode)); //分配孩子节点。
*p={GetVex(G,w),NULL,NULL};
if(first) //w是v 的第一个未被访问的邻接顶点 { //是根的左孩子节点。
T->lchild=p;first=FALSE;
}// if(first)
else //w是v 的其它未被访问的邻接顶点 { //是上一邻接顶点的右兄弟节点。 q->nextsibling=p;
}// else
q=p;
DFSTree(G,w,q); //从第w 个顶点出发深度优先遍历图G ，建立子生成树q 。 }// if(!visited[w])
}// for(w=FirstAdjVex(G,v);
}// DFSTree
7.4.2有向图的强连通分量。 asdfasdfdfasd