采用邻接表实现图的DFS和BFS.docx

include"stdio.h"
#include"stdlib.h"
#define MVNum 30
#define QueueSize 30
#define VexType int
typedef struct ArcNode
{
int adjvex;
struct ArcNode *nextarc;
}ArcNode;
typedef struct VexNode
{
VexType data;
ArcNode *firstarc;
}VexNode,AdjList[MVNum];
typedef struct
{
int vexnumarcnum;
AdjList vertices;
}ALGraph;

int LocateVex(ALGraph *G, VexType v)
{
int i;
for(i=0;i<=G->vexnum;i++)
{
if(G->vertices[i].data==v)
return i;
}
return -1;
}

void CreateGraph(ALGraph *G)
{
int i,j,k;
int v1,v2;
ArcNode *p=NULL,*q=NULL;
printf("请输入顶点数和边数(输入格式为:顶点数 边数)：\n");
scanf("%d%d",&G->vexnum,&G->arcnum);
printf("请输入顶点信息(顶点以1为起始，每个顶点以回车作为结束):\n");
for(i=1;i<=G->vexnum;i++)
{
scanf("%d",&G->vertices[i].data);
G->vertices[i].firstarc=NULL;
}
printf("请输入边的信息(输入格式为:i,j)：\n");
for(k=1;k<=G->arcnum;k++)
{
scanf("%d,%d",&v1,&v2);
i=LocateVex(G,v1);
j=LocateVex(G,v2);
p=(ArcNode*)malloc(sizeof(ArcNode));
if(!p)
exit(1);
p->adjvex=j;
p->nextarc=G->vertices[i].firstarc;
G->vertices[i].firstarc=p;
q=(ArcNode*)malloc(sizeof(ArcNode));
if(!q)
exit(1);
q->adjvex=i;
q->nextarc=G->vertices[j].firstarc;
G->vertices[j].firstarc=q;
}
}

void PrintGraph(ALGraph *G)
{
int i;
ArcNode *p=NULL;
for(i=1;i<=G->vexnum;i++)
{
printf("%d",G->vertices[i].data);
p=(ArcNode*)malloc(sizeof(ArcNode));
if(!p)
exit(1);
p=G->vertices[i].firstarc;
while(p)
{
printf("-->%d",p->adjvex);
p=p->nextarc;
}
printf("\n");
}
}
typedef enum{FALSE,TRUE} Boolean;
Boolean visited[MVNum];
//深度优先搜索
void DFS(ALGraph *G,int i)
{
ArcNode *p;
printf("\nvisit data:%d\n",G->vertices[i].data); // 访问顶点vi
visited[i]=TRUE; //标记vi已访问
p=G->vertices[i].firstarc; //取vi边表的头指针
while(p)
{ //依次搜索vi的邻接点vj，这里j=p->adjvex
if (!visited[p->adjvex]) //若vi尚未被访问
DFS(G,p->adjvex); //则以Vj为出发点向纵深搜索
p=p->nextarc; //找vi的下一邻接点
}
}
void DFSM(ALGraph *G)
{
int i;
for(i=1;i<=G->vexnum ;i++)
visited[i]=FALSE;
for(i=1;i<=G->vexnum ;i++)
if(!visited[i])
DFS(G,i);
}
//广度优先遍历
typedef struct
{
int front;
int rear;
int count;
int data[QueueSize];
}CirQueue;
void InitQueue(CirQueue *Q)
{
Q->front=Q->rear=0;
Q->count=0;
}
int QueueEmpty(CirQueue *Q)
{
return Q->count=QueueSize;
}
int QueueFull(CirQueue *Q)
{
return Q->count==QueueSize;
}
void EnQueue(CirQueue *Q,int x)
{
if (QueueFull(Q))
printf("Queue overflow");
else
{
Q->count++;
Q->data[Q->rear]=x;
Q->rear=(Q->rear+1)%QueueSize;
}
}
int DeQueue(CirQueue *Q)
{
int temp;
if(QueueEmpty(Q))
{
printf("Queue underflow");
return NULL;
}
else
{
temp=Q->data[Q->front];
Q->count--;
Q->front=(Q->front+1)%QueueSize;
return temp;
}
}
void BFS(ALGraph*G,int k)
{
int i;
CirQueue Q; //须将队列定义中DataType改为int
ArcNode *p;
InitQueue(&Q); //队列初始化
printf("\n visit data:%d\n",G->vertices[k].data); //访问源点vk
visited[k]=TRUE;
EnQueue(&Q,k); //vk已访问，将其人队。（实际上是将其序号人队）
while(!QueueEmpty(&Q))
{ //队非空则执行
i=DeQueue(&Q); //相当于vi出队
p=G->vertices[i].firstarc; //取vi的边表头指针
while(p)
{ //依次搜索vi的邻接点vj(令p->adjvex=j)
if(!visited[p->adjvex])
{ //若vj未访问过
printf("\nvisit data:%d\n",G->vertices[p->adjvex].data); //访问vj
visited[p->adjvex]=TRUE;
EnQueue(&Q,p->adjvex); //访问过的vj人队
}
p=p->nextarc; //找vi的下一邻接点
}
}
}
void BFSM(ALGraph *G)
{
int i;
for (i=1;i<=G->vexnum ;i++)
visited[i]=FALSE;
for (i=1;i<=G->vexnum ;i++)
if (!visited[i])
BFS(G,i);
}
void main()
{
int i,x;
ALGraph *G;
G=(ALGraph *)malloc(sizeof(ALGraph));
CreateGraph(G);
PrintGraph(G);
printf("深度优先遍历：");
DFSM(G);
printf("\n");
printf("广度优先遍历：");
BFSM(G);
printf("\n");
}