7.4.1无向图的连通分量和生成树(3)

f(!T) T=p; //是第一棵生成树的根（T的根）。
else q->nextsibling=p; //是其他生成树的根（前一棵的根的"兄弟"）。
q=p; //q指示当前生成树的根。
DFSTree(G,v,p); //建立以p为根的生成树。
}// if(!visited[v])
}// for(v=0;v<G.vexnum;++v)
}// DFSForest

//从第v个顶点出发深度优先遍历图G，建立以T为根的生成树。
void DFSTree(ALGraph G,int v,CSTree &T)
{
visited[v]=TRUE;
bool first=TRUE;
int w;
CSTree p,q;
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};
//
p->data=GetVex(G,w);
p->firstchild=NULL;
p->nextsibling=NULL;
//
if(first) //w是v的第一个未被访问的邻接顶点
{ //是根的左孩子节点。
T->firstchild=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

TElemType GetVex(ALGraph G,int v)
{
return G.vertices[v].data;
//return 'a';
}

//#######################
void LevelOrderTraverse(CSTree T,void(*Visit)(TElemType))
{ //层序遍历树T。
CSTree p;
LinkQueue q;
InitQueue(q);
if(T)
{
printf("--visit_root--\n");//
Visit(Value(T)); //先访问根结点。
EnQueue(q,T);
while(!QueueEmpty(q))
{ //访问
DeQueue(q,p);
if(p->firstchild)
{ //访问当前结点的长子。。
p=p->firstchild;
printf("--visit_firstchild--\n");//
Visit(Value(p));
EnQueue(q,p);//长子入队。
while(p->nextsibling)
{//遍历该长子所有的兄弟。
p=p->nextsibling;
printf("--visit_nextsibling--\n");//
Visit(Value(p));
EnQueue(q,p); //所有兄弟入队。
}
}
}
}
}//LevelOrderTraverse

TElemType Value(CSTree p)
{ //返回结点p所指的值。
return p->data;
}

void vi(TElemType c)
{
printf("-%c-\n",c);
}
//#########################################队列的操作。
Status InitQueue(LinkQueue &Q)
{//构造一个空队列Q。
if(!(Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode))
))
exit(OVERFLOW);
Q.front->next=NULL;
return OK;
}

Status QueueEmpty(LinkQueue Q)
{//判空。
if(Q.rear==Q.front)
return TRUE;
else
r