圖的建立以及周遊（鄰接矩陣法存儲圖）

#include<iostream> 	
#define MVNUM  100	//最大頂點數 
#define MAXQSIZE 100 //隊列的最大長度 
using namespace std;
typedef char VerTexType;	//假設頂點的資料類型為字元型
typedef int	ArcType;	//假設邊的權值類型為整型

bool visited1[MVNUM];//dfs輔助數組 
bool visited2[MVNUM];//bfs輔助數組 
typedef struct
{
	VerTexType vexs[MVNUM]; //頂點表 
	ArcType arcs[MVNUM][MVNUM];//鄰接矩陣
	int vexnum,arcnum;	//圖的目前點數和邊數 
}AMGraph; 
typedef struct{
	int *base;
	int front;
	int rear;
}SqQueue;
bool InitQueue(SqQueue &Q)
{
	Q.base = new int[MAXQSIZE];
	if(!Q.base) return false;
	Q.front = Q.rear = 0;
	return true;
}
bool EnQueue(SqQueue &Q,int e)
{
	if((Q.rear+1)%MAXQSIZE==Q.front) return false;//沾滿
	Q.base[Q.rear] = e;
	Q.rear = (Q.rear+1)%MAXQSIZE;
	return true; 
}
bool DeQueue(SqQueue &Q,int &e)
{
	if(Q.front==Q.rear) return false;//棧空
	e = Q.base[Q.front];
	Q.front=(Q.front+1)%MAXQSIZE;
	return true; 
}
bool QueueEmpty(SqQueue Q)
{
	if(Q.front==Q.rear) return true;//空傳回true,非空傳回false 
	return false;
}


void createUDN(AMGraph &G)
{
	cout<<"請輸入總頂點數:";
	cin>>G.vexnum;//輸入總頂點數，總邊數 
	cout<<"請輸入總邊數:";
	cin>>G.arcnum;
	cout<<"請輸入各頂點資訊：\n"; 
	for(int i=0;i<G.vexnum;++i) {cin>>G.vexs[i];}//依次輸入點的資訊
	cout<<"輸入完成,接下來構造鄰接矩陣\n";
	//初始化鄰接矩陣，邊的權值 均置為極大值MAXINT 
	for(int i=0;i<G.vexnum;++i)
		for(int j=0;j<G.vexnum;++j)
			G.arcs[i][j] = 0;//如果無連接配接，則把值設為0 
	
	 //構造鄰接矩陣 
	 int v1,v2;
	for(int k=0;k<G.arcnum;++k)
	{
		
		cout<<"輸入邊（Vi,Vj）的上下标i,j(空格隔開)：";
		cin>>v1>>v2;
		G.arcs[v2][v1] = 1;
		G.arcs[v1][v2] = 1;
	 } 
 } 
 //輸出鄰接矩陣 
void OutPut(AMGraph &G)
{
	int i,j,count = 0;
	
	for(i = 0;i<G.vexnum;i++)
	{
		for(j=0;j<G.vexnum;j++)
		{
			cout<<G.arcs[i][j]<<" ";
			count++;
			if(count%G.vexnum==0)
			cout<<"\n";	
		}
	}	
}
//深度優先 
void DFS(AMGraph G,int k)
{
 	int j;
 	cout<<G.vexs[k]<<" ";
 	visited1[k] = true;
  
 	for(j = 0 ; j < G.vexnum ; ++j)
 	{
  		if(G.arcs[k][j] != 0 && visited1[j] == 0)
   			DFS(G,j);
 	}
}

//BFS
/*廣度優先周遊*/
void visitEnQueue(AMGraph G,SqQueue &Q,int i)//通路頂點i入隊列Q

{

 	visited2[i]= true; //設定目前頂點通路過
	cout<<G.vexs[i]<<" ";//列印頂點 
	EnQueue(Q,i); //将此頂點入隊列

}

void BFS(AMGraph G)
{ 	
	int i,j;
 	SqQueue Q;
	for(i=0;i<G.vexnum;i++)visited2[i] = false;
 	InitQueue(Q); //初始化一輔助用的隊列
 	for(i=0;i<G.vexnum;i++)//對每一個頂點做循環
	{
		if(!visited2[i]) //若是未被通路過就處理
		{
			visitEnQueue(G,Q,i);//通路頂點i

 			while(!QueueEmpty(Q))//若目前隊列不為空
 			{
				DeQueue(Q,i); //将隊頭元素出隊并賦給i
				for(j=0;j<G.vexnum;j++)
 				{ //判斷其他頂點若與目前頂點存在邊且未被通路過
					if(G.arcs[i][j]==1 && !visited2[j])
						visitEnQueue(G,Q,j);//通路頂點j,并将頂點J入隊 
 				}
 			}

 		}

 	}

}


int main()
{
	AMGraph G;
	createUDN(G);
	cout<<"鄰接矩陣為：\n";
	OutPut(G);
	cout<<"對此圖深度周遊結果是:\n";
	DFS(G,0);
	cout<<endl;
	cout<<"對此圖廣度周遊結果是：\n";
	BFS(G);
}