请大家看看，程序的广度优先遍历没结果输出。
#include "stdio.h"#include"string.h"
#include "malloc.h"
#define OK 1
#define ERROR 0
#define FALSE 0
#define TRUE 1
#define MAX_VERTEX_NUM 20
typedef int Status;
typedef int InfoType;
typedef char VertexType;
int visited[MAX_VERTEX_NUM]={0};
typedef struct ArcNode//弧的结构
{
int adjvex;
struct ArcNode *nextarc;
//InfoType info;
}ArcNode;
typedef struct VNode//顶点的结构
{
VertexType data;
ArcNode * firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct //图的结构
{
AdjList vertices;
int vexnum,arcnum;
//int kind;
}AlGraph;
typedef struct
{
char*base;
int front;
int rear;
}sqQueue;
int initQueue(sqQueue&q)
{
q.base=(char*)malloc( MAX_VERTEX_NUM *sizeof(char));
if(!q.base)
return 0;
q.front=q.rear=0;
return 1;
}
int EnQueue(sqQueue&q,char e)
{
if((q.rear+1)%MAX_VERTEX_NUM ==q.front)
return 0;
q.base[q.rear]=e;
q.rear=(q.rear+1)%MAX_VERTEX_NUM ;
return 1;
}
int DeQueue(sqQueue&q,char e)
{
if(q.front==q.rear)
return 0;
e=q.base[q.front];
q.front=(q.front+1)%MAX_VERTEX_NUM ;
return 1;
}
void CreateGraph(AlGraph &G)//创建邻接表
{
printf("input vexnum and arcnum");
scanf("%d%d",&G.vexnum,&G.arcnum);
printf("input the message of vex");
for(int i=0;i<G.vexnum;i++)//输入顶点信息
{
scanf("%s",&G.vertices[i].data);
G.vertices[i].firstarc=NULL;
}
printf("output the message of hu ");//输入弧的信息
for(i=0;i<G.arcnum;i++)
{
int tail,head;
ArcNode *p,*pnew;
printf("输入弧尾、弧头");
scanf("%d%d",&tail,&head);
pnew=(ArcNode *)malloc(sizeof(ArcNode));
pnew->adjvex=head;
pnew->nextarc=NULL;
p=G.vertices[tail].firstarc;
if(!p)
G.vertices[tail].firstarc=pnew;
else
{
while(p->nextarc!=NULL) p=p->nextarc;
p->nextarc=pnew;
}
}
}
void VisitFunc(AlGraph &G,int v)//访问函数
{
printf("%c",G.vertices[v].data);
}
int FirstAdjvex(AlGraph &G,int v)
{
if(G.vertices[v].firstarc)
return G.vertices[v].firstarc->adjvex;
else
return -1;
}
int NextAdjvex(AlGraph &G,int v,int w)//求下一个邻接点
{
ArcNode *p;
p=G.vertices[v].firstarc;
while(p->adjvex!=w)
p=p->nextarc;
if(p->nextarc)
return p->nextarc->adjvex;
else
return -1;
}
void DFS(AlGraph &G,int v)//一个节点的深度优先遍历
{
visited[v]=TRUE;
VisitFunc(G,v);
for(int w=FirstAdjvex(G,v);w>=0;w=NextAdjvex(G,v,w))
if(!visited[w])
DFS(G,w);
}
void DFSTraverse(AlGraph &G)//图的深度优先遍历
{
printf("深度优先遍历");
for(int v=0;v<G.vexnum;v++)
if(!visited[v])
DFS(G,v);
}
void Bftraverse(AlGraph& G)
{printf("广度优先遍历");
sqQueue q;
initQueue(q);
for(int v=0;v<G.vexnum;v++)
if(!visited[v])
{
visited[v]=TRUE;
VisitFunc(G,v);
EnQueue(q,v);
while(q.front!=q.rear)
{DeQueue(q,v);
for(int w=FirstAdjvex(G,v);w>=0;w=NextAdjvex(G,v,w))
if(!visited[w])
{
visited[w]=TRUE;
VisitFunc(G,w);
EnQueue(q,w);
}
}
}
}
int main()
{
AlGraph G;
CreateGraph(G);
DFSTraverse(G);
Bftraverse(G);
return 0;
}
