邻接表和邻接矩阵手写简洁代码DFS BFS

这是通过邻接矩阵进行DFS
#include<iostream>#include<string> #include<windows.h>#define Max_ver_num 20using namespace std  ;bool visit[Max_ver_num] ;//这个数组的用途是标记struct	HGraph{		string vexs [ Max_ver_num ] ; //放每个顶点的数组的名字		int arcs [Max_ver_num][Max_ver_num]  ; // ；邻接矩阵		int vexnum ;	//顶点的数目		int arcnum ; //边的数目，这边的边是没有权值的		}; int Locate ( HGraph G , string  x ) { //确定顶点的位置		int k = 0;		while(G.vexs[k] != x) {			k++ ;		}		return k ;}void Create (HGraph &G){ //创建一个图，这里的图是指构造无向图，通过邻接矩阵构建	int i = 0 , j , k;	cout <<"输入图的顶点和边的数目: ";	cin >>G.vexnum >>G.arcnum ;	cout <<"依次输入各个顶点的名称 :"; 	while (i<G.vexnum) {		cin >>G.vexs[i++] ;	}	for(i = 0 ; i < G.vexnum;i++){		for(j = 0 ; j < G.vexnum; j ++) {			G.arcs[i][j] = 0 ;		}	}	for( k=0 ;k <G.arcnum ; k++) {			cout <<"输入邻接顶点 ：" ; 			string v1 ,v2 ;			cin >> v1 >>v2		;			i = Locate (G , v1) ;			j = Locate (G , v2) ;			while (i<0 || j<0){				cout <<"输入有误，请重输 :  " ; 				cin >>v1 >> v2 ;				i = Locate (G , v1) ;				j = Locate (G , v2) ;			}			G.arcs [i][j]  = 1 ;			G.arcs[j][i] =G.arcs[i][j]  ; //因为是无向图，所以是互相~;	}			cout <<"done"<<endl;}void DFS(HGraph G , int j ) {		visit[j] = true ;		cout <<G.vexs[j] <<endl;		for(int k = 0 ;k <G.vexnum ; k++) {			if(!visit[k] && G.arcs[j][k]){					DFS(G,k) ;			}			}}void  DFS_tra(HGraph G ) {	for(int i = 0 ; i <G.vexnum ;i++) {		visit [i] = false ;//先把所有的点全都赋成falser ;}	for(int j = 0 ; j <G.vexnum ; j++){		if(!visit[j] ) {				DFS (G , j) ;		}			}}int main () {	HGraph G ;	Create (G) ;	cout <<"DFS 后的顺序为 :"<<endl;	DFS_tra (G) ;	cout<< endl;	system ("pause" ) ;	return 0 ;}
通过邻接表进行BFS，我觉得写得算简单，虽然写的很费劲
#include<iostream>#include<string>#include<queue>#include<windows.h>using namespace std;#define Max 20  bool visit[20] ;//跟前面无向图里面的作用一样，后期用来判断是否被访问过 int Vex_Num; //看到网上都有这个，主要是用来判断是否每个点都访问过了   struct ArcNode{	int adjvex ; //弧所指的顶点位置  	ArcNode *nextarc ;// 指向next ->弧  } ;    typedef struct VNode{  	string data ;//顶点  	ArcNode *firarc ; //顶点出来的第一条狐  }AdjList [Max] ;    struct HGraph{  	AdjList vertices;//头结点数组  	int vexnum;//顶点数  	int arcnum;//边数  } ;    int Locate(HGraph G,string x){  //定位顶点位置 	int v ;	for(v=0;G.vertices[v].data!=x ;v++){					//donothing	};  	return v;  }      void Create(HGraph &G) {		string v1,v2;  	int i , j , k ;  	cout<<"请输入顶点的数目和边的数目：";  	cin>>G.vexnum>>G.arcnum;  	cout<<"请输入顶点名称：";  	for( i=0 ; i<G.vexnum ; i++){  		cin>>G.vertices[i].data;  		G.vertices[i].firarc=NULL;  	}     for(k=0;k<G.arcnum;k++){  		cout<<"end - begin顺序输入边所对应的两个顶点：" ;  		cin>>v1>>v2 ;   		i = Locate(G,v1) ;  		j = Locate(G,v2) ;  		while(i<0|| j<0){  			cout<<"有误，请重新输入: ";  			cin>>v1>>v2;  			i=Locate(G,v1);  			j=Locate(G,v2);   		}  		ArcNode *p=new ArcNode;  		p->adjvex = j ;  		p->nextarc = G.vertices[i].firarc ;  		G.vertices[i].firarc = p ;  	}  }  void BFS_Tra(HGraph G){  	Vex_Num = 0 ;  	int i , k , w ;  	queue<int>q ;  	ArcNode *p ;  	for(i=0 ; i<G.vexnum ;i++){  		visit[i]=false ;//跟之前一样，全部赋为false，表示未访问  	}	for(i=0 ; i<G.vexnum ;i++){  		if(!visit[i]){  			visit[i]=true ;  			cout<<G.vertices[i].data<<"  " ;   Vex_Num+=1 ;  			if(G.vertices[i].firarc)  				 q.push(i) ; //进站  				while( !q.empty() ){  					k=q.front();  					q.pop(); 					for(p=G.vertices[k].firarc;p;p=p->nextarc){  						w=p->adjvex;  						if(!visit[w]){  							visit[w]=true ;  							cout<<G.vertices[w].data<<"  ";   Vex_Num+=1;  							if(Vex_Num==G.vexnum)  								break;  //说明已经全部访问过							if(G.vertices[w].firarc)  									q.push(w);  					}  				}  			}  		}  	}  }//操他妈的觉得图论好难int main  () {	HGraph G;	Create (G) ;	cout <<"经过广度优先遍历后输出的顺序为 ："<<endl; 	BFS_Tra (G) ;	system ("pause") ;}