#include<bits/stdc++.h>
#define MAXV 5 //用另一个数组的时候改成5
#define INF 32767 //定义无穷
#define MaxSize 50
typedef int ElemType;
typedef char InfoType;
//环形队列
typedef struct
{
ElemType data[MaxSize];
int front,rear;
}SqQueue;
typedef struct ANode
{
int adjvex;
struct ANode *nextarc;
int weight;
}ArcNode;
typedef struct Vnode
{
InfoType info;
ArcNode *firstarc;
}VNode;
typedef struct
{
Vnode adjlist[MAXV];
int n,e;
}AdjGraph;
void Create(AdjGraph *&G,int A[MAXV][MAXV],int n,int e)
{
int i,j;
ArcNode *p;
G=(AdjGraph *)malloc(sizeof(AdjGraph));
for(i=0;i<n;i++)
{
G->adjlist[i].firstarc=NULL;
}
for(i=0;i<n;i++)
{
for(j=n-1;j>=0;j--)
{
if(A[i][j]!=0 && A[i][j]!=INF)
{
p=(ArcNode *)malloc(sizeof(ArcNode));
p->adjvex=j;
p->weight=A[i][j];
p->nextarc=G->adjlist[i].firstarc;
G->adjlist[i].firstarc=p;
}
}
}
G->n=n;
G->e=e;
}
void DispAdj(AdjGraph *G)
{
int i;
ArcNode *p;
for(i=0;i<G->n;i++)
{
p=G->adjlist[i].firstarc;
printf("%3d:",i);
while(p!=NULL)
{
printf("%3d[%d]->",p->adjvex,p->weight);
p=p->nextarc;
}
printf("\n");
}
}
//初始化队列
void InitQueue(SqQueue *&q)
{
q=(SqQueue *)malloc(sizeof(SqQueue));
q->front=q->rear=0;
}
//销毁队列
void DestoryQueue(SqQueue *&q)
{
free(q);
}
//判断队列是否为空
bool QueueEmpty(SqQueue *q)
{
return(q->front==q->rear);
}
//入队
bool enQueue(SqQueue *&q,ElemType e)
{
if((q->rear+1)%MaxSize==q->front)
{
return false;
}
q->rear=(q->rear+1)%MaxSize;
q->data[q->rear]=e;
return true;
}
//出队
bool deQueue(SqQueue *&q,ElemType &e)
{
if(q->front==q->rear)
{
return false;
}
q->front=(q->front+1)%MaxSize;
e=q->data[q->front];
return true;
}
//广度优先遍历
void BFS(AdjGraph *G,int v)
{
int w,i;
ArcNode *p;
SqQueue *qu;
InitQueue(qu);
int visited[MAXV];
for(int i=0;i<G->n;i++) visited[i]=0;
printf("%2d",v);
visited[v]=1;
enQueue(qu,v);
while(!QueueEmpty(qu))
{
deQueue(qu,w);
p=G->adjlist[w].firstarc;
while(p!=NULL)
{
if(visited[p->adjvex]==0)
{
printf("%2d",p->adjvex);
visited[p->adjvex]=1;
enQueue(qu,p->adjvex);
}
p=p->nextarc;
}
}
printf("\n");
}
int main()
{
AdjGraph *G;
int A[MAXV][MAXV]={
{0,8,32767,5,32767},
{32767,0,3,32767,32767},
{32767,32767,0,32767,6},
{32767,32767,9,0,32767},
{32767,32767,32767,32767,0}};
/*int A[MAXV][MAXV]={{0,1,1,1,0,0},
{1,0,0,0,1,0},
{1,0,0,0,1,0},
{1,0,0,0,0,1},
{0,1,1,0,0,0},
{0,0,0,1,0,0}};*/
int n=5,e=5; //n和e也要改成6
Create(G,A,n,e);//创建
DispAdj(G);//打印邻接表
BFS(G,0);
return 0;
}
