宽度优先搜索

#include
#include
#include
int visited[20]={0};
typedef struct
{
char vexs[20];/*顶点表*/
int edges[20][20];
int n,e;
}Mgraph;
typedef struct QNode
{
int data;
struct QNode *next;
int Queusize;
}
QNode,*QueuePtr;//定义队列结点类型
typedef struct
{
QueuePtr front;
QueuePtr rear;
}
LinkQueue;//队列的类型
void InitQueue(LinkQueue *Q)//创建队列
{
Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));
Q->front->next=NULL;
}
void EnQueue(LinkQueue *Q,int e)//将元素插入队列
{
QueuePtr p;
p=(QueuePtr)malloc(sizeof(QNode));
p->data=e;
p->next=NULL;
Q->rear->next=p;
Q->rear=p;
}
int DeQueue(LinkQueue *Q)//将元素出列且返回元素的位置
{
int e;
QueuePtr p;
p=Q->front->next;
e=p->data;
Q->front->next=p->next;
if(Q->rear==p)
Q->rear=Q->front;
free(p);
return (e);
}
int QueueEmpty(LinkQueue *Q)//判断队列是否为空
{
if(Q->front==Q->rear )
return 1;
else
return 0;
}
void CreateMGraph(Mgraph *G)
{

int i,j,k;
printf("输入顶点和边数\n");
scanf("%d %d", &G->n,&G->e);
getchar();
printf("输入%d个顶点\n",G->n);
for(i=0;in; i++ )
G->vexs[i]=getchar();
for (i = 0;in; i++)
for (j = 0;j n; j++)
G->edges[i][j]=0;
printf("在矩阵中输入%d个元素:\n",2*(G->e));
for(k = 0;k<2*(G->e);k++)
{
scanf("%d%d",&i,&j);
G->edges[i][j]=1;
}
}
void BFS(Mgraph G,int i)//广度优先遍历
{
int u,j;
LinkQueue Q;
InitQueue(&Q);
printf("%c",G.vexs[i]);
visited[i]=1;//标记
EnQueue(&Q,i);
while(!QueueEmpty(&Q))
{
i=DeQueue(&Q);
for(j=0;j if(G.edges[i][j]==1&&!visited[j])
{ printf("%c",G.vexs[j]);
visited[j]=1;
EnQueue(&Q,j);
}
}

}
void main()
{
Mgraph G;
CreateMGraph(&G);
printf("广度:\n");
BFS(G,0);
}