[分享]详细学习图的遍历实例 - C语言论坛

栖柏

等　级：论坛游民
威　望：3
帖　子：1103
专家分：17
注　册：2007-8-23

楼主

问题点数：0 回复次数：8

[分享]详细学习图的遍历实例

/****本人刚学时的，不要说什么了，喜欢就看看，希望对你有用*****/

1．问题描述

对给定的图结构和起点，产生深度优先遍历和广度优先遍历序列，并给出求解过程动态演示。如一个无向图：（最后的图）

邻接矩阵：
V0 V1 V2 V3 V4 V5 V6 V7

V0 0 1 1 0 0 0 0 0
V1 1 0 0 1 1 0 0 0
V2 1 0 0 0 0 1 1 0
V3 0 1 0 0 0 0 0 1
V4 0 1 0 0 0 0 0 1
V5 0 0 1 0 0 0 1 0
V6 0 0 1 0 0 1 0 0
V7 0 0 0 1 1 0 0 0
总共8个点，9条边。
需要输入的项目：
0 1
0 2
1 3
1 4
2 5
2 6
3 7
4 7
5 6

输出：（从第一个结点开始遍历）
DFS: V0->V1->V3->V7->V4->V2->V5->V6 (1 2 4 8 5 3 6 7)
BFS: V0->V1->V2->V3->V4->V5->V6->V7 (1 2 3 4 5 6 7 8)

2．设计思路

由于图的广度优先搜索需要用到队列，先设计一个关于队列的操作函数（如队列的初始化，销毁，判断队空，入队，出队操作）的头文件QUEUE.h。然后在lili.c的文件中用邻接矩阵表示图的结构，然后进行深度优先遍历和广度优先遍历操作。

3．数据结构设计

/*队列的数据结构*/
typedef int DataType;
typedef struct{
DataType data[MAXSIZE];
int front,rear;
}SeqQueue,*PSeqQueue;

/*图的数据结构*/
typedef char VexType;
typedef char EdgeType;
typedef struct{
VexType vexs[MAXNUM];
EdgeType edges[MAXNUM][MAXNUM];
int n,e;
}MGraph;

4．功能函数设计

（1）队列操作头文件QUEUE.h中
PSeqQueue Init_SeqQueue()/*队列初始化*/
void Destroy_SeqQueue(PSeqQueue *Q)/*销毁队列*/
int Empty_SeqQueue(PSeqQueue Q)/*判断队空*/
int In_SeqQueue(PSeqQueue Q,DataType x)/*入队*/
int Out_SeqQueue(PSeqQueue Q,DataType *x)/*出队*/

（2）图的遍历lili.c中
void CreatGraph(MGraph *G,int vexnum)/*图的建立，用邻接矩阵表示*/
int FirstAdjvex(MGraph *G,int vex)/*获取第一个未被访问的邻接节点*/
int NextAdjvex(MGraph *G,int vex)/*获取下一个未被访问的邻接节点*/
void DFS(MGraph *G,int vex)/*从第vex个顶点深度优先搜索*/
void DFSt(MGraph *G)/*深度优先搜索*/
void BFS(MGraph *G,int vex)/*从第vex个顶点广度优先搜索*/
void BFSt(MGraph *G)/*广度优先搜索*/
int main()/*主函数*/

5．编码实现

（1） QUEUE.h文件

/*队列操作头文件*/
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 30

/****************/
/*队列的数据结构*/
typedef int DataType;
typedef struct{
DataType data[MAXSIZE];
int front,rear;
}SeqQueue,*PSeqQueue;
/***************/

PSeqQueue Init_SeqQueue()/*队列初始化*/
{
PSeqQueue Q;
Q=(PSeqQueue)malloc(sizeof(SeqQueue));
if(Q)
{
Q->front=0;
Q->rear=0;
}
return Q;
}

void Destroy_SeqQueue(PSeqQueue *Q)/*销毁队列*/
{
if(*Q)
free(*Q);
*Q=NULL;
}

int Empty_SeqQueue(PSeqQueue Q)/*判断队空*/
{
if(Q&&Q->front==Q->rear)
return(1);
else
return(0);
}

int In_SeqQueue(PSeqQueue Q,DataType x)/*入队*/
{
if((Q->rear+1)%MAXSIZE==Q->front)
{
printf("Queue Full!");
return(-1);
}
else
{
Q->rear=(Q->rear+1)%MAXSIZE;
Q->data[Q->rear]=x;
return(1);
}
}

int Out_SeqQueue(PSeqQueue Q,DataType *x)/*出队*/
{
if(Empty_SeqQueue(Q))
{
printf("Queue Empty");
return(-1);
}
else
{
Q->front=(Q->front+1)%MAXSIZE;
*x=Q->data[Q->front];
return(1);
}
}

（2） lili.c文件

#include<stdio.h>
#include<stdlib.h>
#include<QUEUE.h>/*关于队列的头文件*/
#define MAXNUM 30

/******************/
/*图的数据结构*/
int visted[MAXNUM];/*标志向量*/
typedef char VexType;
typedef char EdgeType;

typedef struct{
VexType vexs[MAXNUM];
EdgeType edges[MAXNUM][MAXNUM];
int n,e;
}MGraph;
/******************/

void CreatGraph(MGraph *G,int vexnum)/*图的建立，用邻接矩阵表示*/
{
int i,j,k,w;
int m,n;
char ch;
G->n=vexnum;
printf("input edge number:\n");
scanf("%d",&(G->e));
printf("your vextex name(*IsNumber*):\n");/*输入顶点代号名称，注意为数字整型*/
for(i=0;i<G->n;i++)
scanf("%d",&(G->vexs[i]));
for(i=0;i<G->n;i++)/*初始化邻接矩阵*/
for(j=0;j<G->n;j++)
G->edges[i][j]=0;
printf("Adjacency Matria(->0 1<=>v0&v1 hava edge<-):\n");
/*输入边建立矩阵*/
for(k=0;k<G->e;k++)
{
scanf("%d %d",&m,&n);
G->edges[m][n]=1;
G->edges[n][m]=1;
}
printf("You input Adjacency Matria is:\n");/*输出你所输入的矩阵*/
for(i=0;i<G->n;i++)
printf("\t%d",G->vexs[i]);
printf("\n");
for(i=0;i<G->n;i++)
{ printf("%d",G->vexs[i]);
for(j=0;j<G->n;j++)
printf("\t%d",G->edges[i][j]);
printf("\n");
}
}

int FirstAdjvex(MGraph *G,int vex)/*获取第一个未被访问的邻接节点*/
{
int i,k;
for(i=0;i<G->n;i++)
{
if(G->edges[vex][i]==1&&visted[i]==0)
{
k=i;
break;
}
else
k=0;
}
return k;
}

int NextAdjvex(MGraph *G,int vex)/*获取下一个未被访问的邻接节点*/
{
int k;
k=FirstAdjvex(G,vex);
return k;
}

void DFS(MGraph *G,int vex)/*从第vex个顶点深度优先搜索*/
{
int w;
printf("%d ",G->vexs[vex]);
visted[vex]=1;/*访问第vex个顶点，并把访问标志设为1*/
for(w=FirstAdjvex(G,vex);w>0;w=NextAdjvex(G,w))
if(!visted[w])/*对未访问的邻接顶点w递归调用DFS*/
DFS(G,w);
}

void DFSt(MGraph *G)/*深度优先搜索*/
{
int i;
for(i=0;i<G->n;i++)
visted[i]=0;/*标志向量初始化*/
for(i=0;i<G->n;i++)
if(!visted[i])/*vi未访问过，从vi开始DFS搜索*/
DFS(G,i);
printf("\n");
}

void BFS(MGraph *G,int vex)/*从第vex个顶点广度优先搜索*/
{
int i,j;
PSeqQueue Q;
Q=Init_SeqQueue();
printf("%d ",G->vexs[vex]);/*访问*/
visted[vex]=1;
In_SeqQueue(Q,vex);/*原点入队*/
while(!Empty_SeqQueue(Q))
{
Out_SeqQueue(Q,&i);/*vi出队*/
for(j=0;j<G->n;j++)/*依次搜索vi的邻接点*/
if(G->edges[i][j]==1&&!visted[j])
{
printf("%d ",G->vexs[j]) ;/*访问vj*/
visted[j]=1;
In_SeqQueue(Q,j);/*访问过的vj入队*/
}
}
}

void BFSt(MGraph *G)/*广度优先搜索*/
{
int i,v;
for(v=0;v<G->n;v++)
visted[v]=0;/*标志向量初始化*/
for(i=0;i<G->n;i++)
if(!visted[i])/*vi未访问过，从vi开始BFS搜索*/
BFS(G,i);
printf("\n");
}

int main()
{
int num,n,vex;
MGraph *G=(MGraph *)malloc(sizeof(MGraph));
printf("Please input vextex number:\n");
scanf("%d",&num);/*输入顶点数*/
CreatGraph(G,num);
do{/*选择搜索类型*/
printf("->1.use DFS graph\n");
printf("->2.use BFS graph\n");
printf("->0.exit system!\n");
printf("choose your select:\n");
scanf("%d",&n);
switch(n)
{
case 1:
printf("\n--Your DFS IS:\n");
DFSt(G);
break;
case 2:
printf("--Your BFS IS:\n");
BFSt(G);
break;
case 0:
exit(0);
}
}while(n!=0||n!=1||n!=2);
return(0);
}