#include<iostream.h>
#include<stdio.h>
//頭函數(shù)定義


const int max_vexnum=100;                                //最大結(jié)點(diǎn)數(shù)
int vexnum,arcnum;                                       //結(jié)點(diǎn)數(shù)和邊數(shù)
int matrix[max_vexnum][max_vexnum];                      //鄰接矩陣
int consult[max_vexnum];                                 //用于標(biāo)志結(jié)點(diǎn)是否被訪問過
char temp[max_vexnum];                                   //用來存儲結(jié)點(diǎn)的名字
int exist=0;                           //用于標(biāo)志圖是否存在，若不存在則為0，若存在為1



struct Queue{int qa;                                      
             int qe;
             int item[max_vexnum];
}queue;                                                   
//廣度優(yōu)先遍歷時用到的隊列





char Menu();                                           //用戶輸入時的提示
void Init(int vexnum);                                 //初始化標(biāo)志數(shù)組
void Creatmatrix();                                    //建立鄰接矩陣
void Dfs(int start);                                   //深度優(yōu)先遍歷
void Bfs(int start);                                   //廣度優(yōu)先遍歷
//需要調(diào)用的函數(shù)聲明





//*******************************************************************************************
//*******************************************主函數(shù)******************************************
//*******************************************************************************************
void main()
{   cout<<"***************************歡迎使用無向圖的遍歷***************************"<<endl;
	int start;
    char choice;
	choice=Menu();
	while(choice!='4'){
	  switch(choice)
	  {
	  case '1':Creatmatrix();break;
	  case '2':{
		  if(exist==0)
		  {cout<<"沒有圖可以遍歷，請先建立一個新圖"<<endl;break;}
          cout<<"你選擇的是深度優(yōu)先遍歷.你需要從哪個結(jié)點(diǎn)開始遍歷?"<<endl;
		  cout<<"請輸入該結(jié)點(diǎn)的編號:"<<endl;
          cin>>start;
		  Init(vexnum);start--;
		  Dfs(start);}break;
	  case '3':{
		      if(exist==0)
			{cout<<"沒有圖可以遍歷，請先建立一個新圖"<<endl;break;}
		   cout<<"你選擇的是廣度優(yōu)先遍歷.你需要從哪個結(jié)點(diǎn)開始遍歷?"<<endl;
		   cout<<"請輸入該結(jié)點(diǎn)的編號:"<<endl;
		   cin>>start;start--;Init(vexnum);
		   Bfs(start);break;}
	  default:cout<<"對不起，你輸入指令有誤！！！請重新選擇操作。"<<endl;break;
	  }
	choice=Menu();
	}
getchar();
}




//用戶輸入時的提示
char Menu()
{char choice;
 cout<<endl<<"請輸入你的選擇:"<<endl;
 cout<<"1.建立一個新的無向圖."<<endl;
 cout<<"2.按深度優(yōu)先進(jìn)行遍歷."<<endl;
 cout<<"3.按廣度優(yōu)先進(jìn)行遍歷."<<endl;
 cout<<"4.退出程序."<<endl;
 cin>>choice;
return (choice);
}





//初始化標(biāo)志數(shù)組
void Init(int vexnum)
{int i=1;
	for(;i<=vexnum;i++)
	 consult[i]=0;
}                                                            //全部初始化為零，未被訪問過





//建立鄰接矩陣
void Creatmatrix()
{ cout<<"請分別輸入新建的圖的結(jié)點(diǎn)數(shù)和邊數(shù)"<<endl;
  cin>>vexnum>>arcnum;
  int vn=vexnum;int an=arcnum;
  if(vexnum>max_vexnum)
  {cout<<"對不起,本程序所能建立圖的最大結(jié)點(diǎn)數(shù)為100"<<endl;return;}
  else if(an>(vn*(vn-1)/2))                                 //邊總數(shù)溢出
  {cout<<"這樣的圖不存在請重新操作"<<endl;return;}
  
  int t=0;
  cout<<"請輸入結(jié)點(diǎn)(請記住編號)"<<endl;
  for(;t<vn;t++)
	 { cout<<"請輸入第"<<t+1<<"個結(jié)點(diǎn)的名稱：";
       cin>>temp[t];}
  int i=0,j=0,k=0;char t1,t2;
  for(;i<vn;i++)
	 for(;j<vn;j++)
		 matrix[i][j]=NULL;                                    //初始化鄰接矩陣
  for(;k<an;k++)
  {cout<<"請輸入第"<<k+1<<"條邊的兩個結(jié)點(diǎn)（直接輸入中間不需空格）:"<<endl;
    cin>>t1>>t2;
	for(t=0;(t<vn)&&(t1!=temp[t]);t++);
	i=t;                                                       //尋找t1對應(yīng)結(jié)點(diǎn)的位置
	for(t=0;(t<vn)&&(t2!=temp[t]);t++);
	j=t;                                                       //尋找t2對應(yīng)結(jié)點(diǎn)的位置
    matrix[i][j]++;matrix[j][i]++;}
  cout<<endl<<"所建無向圖的鄰接矩陣為:"<<endl<<endl;
  for(t=0;t<vexnum;t++)
  cout<<temp[t]<<"   ";
   cout<<endl<<endl;
   for(i=0;i<vn;i++)
	 {for(j=0;j<vn;j++)
		 cout<<matrix[i][j]<<"   ";
  cout<<endl;}
  exist=1;                                                     //說明圖存在
}





//深度優(yōu)先遍歷
void Dfs(int start)
{int j=0;
 cout<<temp[start]<<"---";
 consult[start+1]=1;                                        //在標(biāo)志數(shù)組中標(biāo)志為訪問過
 for(;j<vexnum;j++)
	 if((matrix[start][j]==1)&&(consult[j+1]==0)) 
		 Dfs(j);                                             //對未被訪問的下一結(jié)點(diǎn)進(jìn)行遞歸調(diào)用
}





//廣度優(yōu)先遍歷
void Bfs(int start)
{if(exist==0){cout<<"沒有圖可以遍歷，請先建立一個新的無向圖"<<endl;return;}
 int j;int s;
 consult[start+1]=1;
 cout<<temp[start]<<"---";
 queue.qa=0;
 queue.qe=0;
 queue.item[0]=start;                                       //進(jìn)入隊列
  while(queue.qa<=queue.qe)
  {s=queue.item[queue.qa++];                                //出隊列
	for(j=0;j<vexnum;j++)
	{if((matrix[s][j]==1)&&(consult[j+1]==0))
	{cout<<temp[j]<<"---";consult[j+1]=1;
	queue.item[++queue.qe]=j;}                              //進(jìn)隊列
	}
  }
}