graph.cpp

数据结构中关于图的遍历

#include<iostream.h>
#include<stdio.h>
//头函数定义


const int max_vexnum=100;                                //最大结点数
int vexnum,arcnum;                                       //结点数和边数
int matrix[max_vexnum][max_vexnum];                      //邻接矩阵
int consult[max_vexnum];                                 //用于标志结点是否被访问过
char temp[max_vexnum];                                   //用来存储结点的名字
int exist=0;                           //用于标志图是否存在，若不存在则为0，若存在为1



struct Queue{int qa;                                      
             int qe;
             int item[max_vexnum];
}queue;                                                   
//广度优先遍历时用到的队列





char Menu();                                           //用户输入时的提示
void Init(int vexnum);                                 //初始化标志数组
void Creatmatrix();                                    //建立邻接矩阵
void Dfs(int start);                                   //深度优先遍历
void Bfs(int start);                                   //广度优先遍历
//需要调用的函数声明





//*******************************************************************************************
//*******************************************主函数******************************************
//*******************************************************************************************
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<<"你选择的是深度优先遍历.你需要从哪个结点开始遍历?"<<endl;
		  cout<<"请输入该结点的编号:"<<endl;
          cin>>start;
		  Init(vexnum);start--;
		  Dfs(start);}break;
	  case '3':{
		      if(exist==0)
			{cout<<"没有图可以遍历，请先建立一个新图"<<endl;break;}
		   cout<<"你选择的是广度优先遍历.你需要从哪个结点开始遍历?"<<endl;
		   cout<<"请输入该结点的编号:"<<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.按深度优先进行遍历."<<endl;
 cout<<"3.按广度优先进行遍历."<<endl;
 cout<<"4.退出程序."<<endl;
 cin>>choice;
return (choice);
}





//初始化标志数组
void Init(int vexnum)
{int i=1;
	for(;i<=vexnum;i++)
	 consult[i]=0;
}                                                            //全部初始化为零，未被访问过





//建立邻接矩阵
void Creatmatrix()
{ cout<<"请分别输入新建的图的结点数和边数"<<endl;
  cin>>vexnum>>arcnum;
  int vn=vexnum;int an=arcnum;
  if(vexnum>max_vexnum)
  {cout<<"对不起,本程序所能建立图的最大结点数为100"<<endl;return;}
  else if(an>(vn*(vn-1)/2))                                 //边总数溢出
  {cout<<"这样的图不存在请重新操作"<<endl;return;}
  
  int t=0;
  cout<<"请输入结点(请记住编号)"<<endl;
  for(;t<vn;t++)
	 { cout<<"请输入第"<<t+1<<"个结点的名称：";
       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<<"条边的两个结点（直接输入中间不需空格）:"<<endl;
    cin>>t1>>t2;
	for(t=0;(t<vn)&&(t1!=temp[t]);t++);
	i=t;                                                       //寻找t1对应结点的位置
	for(t=0;(t<vn)&&(t2!=temp[t]);t++);
	j=t;                                                       //寻找t2对应结点的位置
    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;                                                     //说明图存在
}





//深度优先遍历
void Dfs(int start)
{int j=0;
 cout<<temp[start]<<"---";
 consult[start+1]=1;                                        //在标志数组中标志为访问过
 for(;j<vexnum;j++)
	 if((matrix[start][j]==1)&&(consult[j+1]==0)) 
		 Dfs(j);                                             //对未被访问的下一结点进行递归调用
}





//广度优先遍历
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;                                       //进入队列
  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;}                              //进队列
	}
  }
}