把以前写过的图的广度优先搜索分享给大家（C语言版）
#include<stdio.h>
#include<stdlib.h>
#define MAX_VERTEX_NUM 20
#define MAXQSIZE 100
#define OK 1
typedef char VertexType;
typedef int QElemType; typedef struct ArcNode//边结点
{
int adjvex;
struct ArcNode *nextarc;
}ArcNode; typedef struct VNode//定义头数组
{
VertexType data;
ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM]; typedef struct ALGraph//定义图
{
AdjList vertices;
int vernum,arcnum;
}ALGraph; typedef struct SqQueue
{
QElemType *base;
int front;
int rear;
}SqQueue; int CreateDG(ALGraph &G)
{
int i,j,k,v1,v2;
ArcNode *p;
printf("请输入图的节点数：");
scanf("%d",&G.vernum );
printf("请输入图的边的个数：");
scanf("%d",&G.arcnum);
for(i=;i<G.vernum;i++)
{
printf("请输入第%d个顶点数据：",i+);
getchar();
scanf("%c",&G.vertices[i].data);
//G.vertices[i].data=i;
G.vertices[i].firstarc=NULL;
}
printf("请输入节点的边关系，如：结点1和结点2有边就输入1和2（每条边就输入一次）：\n");
for(k=;k<G.arcnum;k++)
{
printf("请输入第%d条边的一个结点：",k+);
scanf("%d",&v1);
printf("请输入第%d条边的另一个结点：",k+);
scanf("%d",&v2);
printf("\n");
i=v1;
j=v2;
while(i<||i>G.vernum||j<||j>G.vernum)
{
printf("请输入第%d条边的一个结点：",k+);
scanf("%d",&v1);
printf("请输入第%d条边的一个结点：",k+);
scanf("%d",&v2);
printf("\n");
i=v1;
j=v2;
}
p=(ArcNode *)malloc(sizeof(ArcNode));
if(!p)
{
printf("分配内存失败！\n");
return ;
}
p->adjvex=j-;
p->nextarc=G.vertices[i-].firstarc;
G.vertices[i-].firstarc=p;
}
return OK;
}
int InitQueue(SqQueue &Q)
{
Q.base=(QElemType *)malloc(MAXQSIZE*sizeof(QElemType));
if(!Q.base)
{
printf("队列内存失败！\n");
return ;
}
Q.front=Q.rear=;
return (OK);
} int EnQueue(SqQueue &Q,QElemType e)
{
if((Q.rear+)%MAXQSIZE==Q.front)
{
printf("队列已满!\n");
return ;
}
Q.base[Q.rear]=e;
Q.rear=(Q.rear+)%MAXQSIZE;
return (OK);
}
int QueueEmpty(SqQueue Q)
{
if(Q.front==Q.rear)
return (OK);
else
return ;
} int DeQueue(SqQueue &Q,QElemType &e)
{
if(Q.front==Q.rear)
{
printf("队列为空！无法删除！\n");
return ;
}
e=Q.base[Q.front];
Q.front=(Q.front+)%MAXQSIZE;
return (e);
}
void BFSTraverse(ALGraph G)
{
int i,j,k;
int visited[MAX_VERTEX_NUM];
ArcNode *p;
SqQueue Q;
for(i=;i<G.vernum;i++)
visited[i]=;
InitQueue(Q);
for(i=;i<G.vernum;i++)
{
if(visited[i]==)
{
visited[i]=;
printf("%c-->",G.vertices[i].data);
EnQueue(Q,i);
while(!QueueEmpty(Q))
{
DeQueue(Q,j);
for(k=j,p=G.vertices[j].firstarc;p!=NULL;k=p->adjvex,p=p->nextarc)
{
if(visited[k]==)
{
visited[k]=;
printf("%c-->",G.vertices[k].data);
EnQueue(Q,k);
}
}
}
}
}
}
int main()
{
ALGraph G;
CreateDG(G); printf("广度优先搜索结果为\n开始-->");
BFSTraverse(G);
printf("结束!\n");
return ;
}
运行结果截图: