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

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

eturn FALSE;
}

Status EnQueue(LinkQueue &Q,QElemType e)
{//将元素e入队。
QueuePtr p;
if(!(p=(QueuePtr)malloc(sizeof(QNode))))
exit(OVERFLOW);
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p; //注意此步！ 先连接上，后转移。
return OK;
}

Status DeQueue(LinkQueue &Q,QElemType &e)
{//队头元素出列，并用e返回其值。
QueuePtr p;
if(Q.front==Q.rear)
return ERROR;
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p) //队列中只有一个元素。
Q.rear=Q.front;
free(p);
return OK;
}
//////////////////////////////////////////////
-------beg-----
-0#a--->d--->b
-1#b--->e--->c--->a
-2#c--->e--->d--->b
-3#d--->c--->a
-4#e--->c--->b
------------------------in_main_before_DFSTraverse--
-in_DFSTraverse-j=0-
v=a
-in_DFS1-v=0,w=3-
v=d
-in_DFS1-v=3,w=2-
v=c
-in_DFS1-v=2,w=4-
v=e
-in_DFS1-v=4,w=1-
v=b
-in_DFS2-v=4,w=1-
-in_DFS2-v=2,w=4-
-in_DFS2-v=3,w=2-
-in_DFS2-v=0,w=3-
------------------------in_main_before_DFSForest--
--in_DFSForest_GetVex(G,v)=a--
-----------------------------------------before_LevelOrderTraverse--
--visit_root--
-a-
--visit_firstchild--
-d-
--visit_firstchild--
-c-
--visit_firstchild--
-e-
--visit_firstchild--
-b-
-------end-----
Press any key to continue
//////////////////////////////////////////////
============================================================
e2:建立无向图的深度优先森林(DFSForest,G2)，另一种遍历顺序.
......其它代码同上。
void CreateGraph(ALGraph &G)
{
int i, j = 0, k = 0;
char hand, tide;
ArcNode *p;
char vertices[]={'a','b','c','d','e'};
char head[]={'a','a','b','b','c','c'};
char tail[]={'d','b','e','c','d','e'};
//v1v2,v1v4,23,25,34,35,
...
}
......
//////////////////////////////////////////////
-------beg-----
-0#a--->b--->d
-1#b--->c--->e--->a
-2#c--->e--->d--->b
-3#d--->c--->a
-4#e--->c--->b
------------------------in_main_before_DFSTraverse--
-in_DFSTraverse-j=0-
v=a
-in_DFS1-v=0,w=1-
v=b
-in_DFS1-v=1,w=2-
v=c
-in_DFS1-v=2,w=4-
v=e
-in_DFS2-v=2,w=4-
-in_DFS1-v=2,w=3-
v=d
-in_DFS2-v=2,w=3-
-in_DFS2-v=1,w=2-
-in_DFS2-v=0,w=1-
------------------------in_main_before_DFSForest--
--in_DFSForest_GetVex(G,v)=a--
-----------------------------------------before_LevelOrderTraverse--
--visit_root--
-a-
--visit_firstchild--
-b-
--visit_firstchild--
-c-
--visit_firstchild--
-e-
--visit_nextsibling--
-d-
-------end-----
Press any key to continue
//////////////////////////////////////////////
============================================================
e3:建立无向图的深度优先森林(DFSForest,G4,和word中顺序一样).
......其他代码同上。
void CreateGraph(ALGraph &G)
{
int i, j = 0, k = 0;
char hand, t
ide;
ArcNode *p;
char vertices[]={'a','b','c','d','e','f','g','h'};
char head[]={'a','a','b','b','c','c','f','d','e'};
char tail[]={'c','b'

,'e','d','g','f','g','h','h'};
//v1v2,v1v4,23,25,34,35,

//cout<<"input the number for vexnum and arcnum:";
//cin>>G.vexnum>>G.arcnum;
G.vexnum =8;
G.arcnum =9;
//cout<<endl;
... ...
}
......
//////////////////////////////////////////////
-------beg-----
--hand=a,tide=c--
--hand=a,tide=b--
--hand=b,tide=e--
--hand=b,tide=d--
--hand=c,tide=g--
--hand=c,tide=f--
--hand=f,tide=g--
--hand=d,tide=h--
--hand=e,tide=h--
------------------------in_main_after_CreateGraph--
-0#a--->b--->c
-1#b--->d--->e--->a
-2#c--->f--->g--->a
-3#d--->h--->b
-4#e--->h--->b
-5#f--->g--->c
-6#g--->f--->c…… 此处隐藏：4013字，全部文档内容请下载后查看。喜欢就下载吧 ……