資料結構——圖的廣度優先周遊（鄰接矩陣法）

#include<stdio.h>
#include<stdlib.h>
#include<queue>
#define INFINITY 65535
typedef int Status;
using namespace std; 
#define MaxVerexNum 100
queue<int>q;
typedef struct
{
	int Vex[MaxVerexNum];//頂點的數目
	int Edge[MaxVerexNum][MaxVerexNum];//鄰接矩陣
	int vexnum,arcnum;//圖目前的頂點數和弧數 
}MGraph;//圖的鄰接矩陣定義
typedef struct QNode
{
	int data;
	struct QNode *next;
}QNode,*QueuePtr;
 
typedef struct
{
	QueuePtr front,rear;  //隊頭隊尾指針 
}LinkQueue;

//建立空隊列
Status InitQueue(LinkQueue &Q)
{
	Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
	if(!Q.front)
		exit(0);
	Q.front->next=NULL;
	return 1;	
} 
 
//入隊列
//将s作為新元素加入隊尾 
Status EnQueue(LinkQueue &Q,int i)
{
	QueuePtr s;
	s=(QueuePtr)malloc(sizeof(QNode));
	if(!s)
		exit(0);
	s->data=i;
	s->next=NULL;
	Q.rear->next=s;
	Q.rear=s;
	return 1;	
}
 
//檢驗是否為空
Status QueueEmpty(LinkQueue Q)
{
	if(Q.front->next==NULL)
		return 0;
	else
		return 1;	
 } 
 
//出隊列
Status DeQueue(LinkQueue *Q,int *i)
{
	QueuePtr p;
	if(Q->front==Q->rear)
		return 0;
	p=Q->front->next;     //該寫法值得商榷
						//相當于p儲存第一個結點
	*i=p->data;
	Q->front->next=p->next;
	
	if(p==Q->rear)   //若隊頭是隊尾	,删除後将rear指向頭結點		
		Q->rear==Q->front;
	free(p);
	return 1;			
 } 

void BFS(MGraph G)
{
	int i,j;
	LinkQueue Q;//初始化隊列 
	int visited[G.vexnum];//通路标記數組 
	for(i=1;i<=G.vexnum;i++)
	{
		visited[i]=0;//初始化标記數組 
	}
	InitQueue(Q);
	for(i=1;i<=G.vexnum;i++)
	{
		if(visited[i]==0)
		{
	printf("%d\t",i);//通路目前節點
	visited[i]=1;
	EnQueue(Q,i);
	 while(!QueueEmpty(Q))
	 {
	 	DeQueue(&Q,&i);
	 	for(j=1;j<G.vexnum;j++)
	 	{
	 		if(G.Edge[i][j]==1&&visited[j]==0)
	 		{
	 			visited[j]=1;
	 			printf("%d\t",j);
	 			EnQueue(Q,j);
			 }
		 }
	 }
}
}
}
int main()
{
	MGraph G;
	int i,j;
	G.vexnum=5;
	G.arcnum=6;
	for(i=1;i<=5;i++)
	{
		for(j=1;j<=5;j++)
		{
			G.Edge[i][j]=0;
		}
	}
	G.Edge[1][2]=G.Edge[2][1]=1;
	G.Edge[1][4]=G.Edge[4][1]=1;
	G.Edge[2][3]=G.Edge[3][2]=1;
	G.Edge[2][5]=G.Edge[5][2]=1;
	G.Edge[3][4]=G.Edge[4][3]=1;
	G.Edge[3][5]=G.Edge[5][3]=1;
	BFS(G);//進行廣度優先周遊 
	return 0;
}