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

b','c','d','e'};
char head[]={'a','a','b','b','c','c'};
char tail[]={'b','d','c','e','d','e'};
//v1v2,v1v4,23,25,34,35,

//cout<<"input the number for vexnum and arcnum:";
//cin>>G.vexnum>>G.arcnum;
G.vexnum =5;
G.arcnum =6;
//cout<<endl;
//cout<<"input"<<G.vexnum<<"char for vexs:";
for(i=0; i < G.vexnum; i++) //输入顶点数据。
G.vertices[i].data=vertices[i];

//cout<<endl;
for(i=0;i<G.vexnum;++i)
G.vertices[i].firstarc=NULL;//初始化顶点指针。

//cout<<"input"<<G.arcnum<<"arc(char-enter-char):"<<endl;
j = 0;
k = 0;
for(i=0; i < G.arcnum; i++) //输入弧数据。
{
//cout<<i<<":";
//cin>>hand;
//cin>>tide;
hand=head[i];
tide=tail[i];
while (hand != G.vertices[j].data)
j++;
while (tide != G.vertices[k].data)
k++;
p=new ArcNode;
p->adjvex=j;
p->nextarc=G.vertices[k].firstarc;
G.vertices[k].firstarc=p;
p=new ArcNode;
p->adjvex=k;
p->nextarc=G.vertices[j].firstarc;
G.vertices[j].firstarc=p;

j = 0;
k = 0;
//cout<<endl;
}
}//CreateGraph
//深度遍历G。
void DFSTraverse(ALGraph G, Status (*Visit)(int v))
{
int j;
VisitFunc = Visit;
for( j=0; j<G.vexnum; j++)
visited[j] = 0;
for(j=0; j<G.vexnum; j++)
if(!visited[j])
{
printf("-in_DFSTraverse-j=%d-\n",j);
DFS(G, j);
}
}//DFSTraverse
//从顶点v开始，访问G(和v连通的)。
void DFS(ALGraph G, int v)
{
int w;
visited[v]=1;
VisitFunc(v);
for(w=FirstAdjVex(G, v); w; w=NextAdjVex(G, v, w))
{
printf("-in_DFS1-v=%d,w=%d-\n",v,w);
if(!visited[w])
DFS(G, w);
printf("-in_DFS2-v=%d,w=%d-\n",v,w);
}
}//DFS

//返回第v个顶点的第一个邻接点。
int FirstAdjVex(ALGraph G, int v)
{
ArcNode *p;
p = G.vertices[v].firstarc;
while(p != NULL)
{
if(visited[p->adjvex] != 1)
return p->adjvex;
p = p->nextarc;
}
return 0;
}//FirstAdjVex

//返回第v个顶点，相对于第w个顶点的邻接点。
int NextAdjVex(ALGraph G, int v, int w)
{
ArcNode *p;
p = G.vertices[v].firstarc;
while(p != NULL)
{
if(visited[p->adjvex] != 1 && p->adjvex != w)
return p->adjvex;
p = p->nextarc;
}
return 0;
}//NextAdjVex

Status printGraph(int v)
{
printf("v=%c", v + 'a');
//cout<<endl;
printf("\n");
return 1;
}
//######################################树的操作。
//建立无向图G的深度优先生成森林的
//（最左）孩子（右）兄弟链表T。
void DFSForest(ALGraph G,CSTree &T)
{
T=NULL;
int v;
CSTree p,q;
for(v=0;v<G.vexnum;++v)
visited[v]=FALSE;
for(v=0;v<G.vexnum;++v)
{
if(!visited[v]) //第v顶点为新的生成树的根节点。
{
p=(CSTree)malloc(sizeof(CSNode)); //分配根节点。
//*p={GetVex(G,v),NULL,NULL}; //给该节点赋值。
p->data=GetVex(G,v);
p->firstchild=NULL;
p->nextsibling=NULL;
printf("--in_DFSForest_GetVex(G,v)=%c--\n",GetVex(G,v));
i