鄰接表和鄰接矩陣手寫簡潔代碼DFS BFS

這是通過鄰接矩陣進(jìn)行DFS
#include<iostream>#include<string> #include<windows.h>#define Max_ver_num 20using namespace std  ;bool visit[Max_ver_num] ;//這個數(shù)組的用途是標(biāo)記struct	HGraph{		string vexs [ Max_ver_num ] ; //放每個頂點(diǎn)的數(shù)組的名字		int arcs [Max_ver_num][Max_ver_num]  ; // ；鄰接矩陣		int vexnum ;	//頂點(diǎn)的數(shù)目		int arcnum ; //邊的數(shù)目，這邊的邊是沒有權(quán)值的		}; int Locate ( HGraph G , string  x ) { //確定頂點(diǎn)的位置		int k = 0;		while(G.vexs[k] != x) {			k++ ;		}		return k ;}void Create (HGraph &G){ //創(chuàng)建一個圖，這里的圖是指構(gòu)造無向圖，通過鄰接矩陣構(gòu)建	int i = 0 , j , k;	cout <<"輸入圖的頂點(diǎn)和邊的數(shù)目: ";	cin >>G.vexnum >>G.arcnum ;	cout <<"依次輸入各個頂點(diǎn)的名稱 :"; 	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 <<"輸入鄰接頂點(diǎn) ：" ; 			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]  ; //因?yàn)槭菬o向圖，所以是互相~;	}			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 ;//先把所有的點(diǎn)全都賦成falser ;}	for(int j = 0 ; j <G.vexnum ; j++){		if(!visit[j] ) {				DFS (G , j) ;		}			}}int main () {	HGraph G ;	Create (G) ;	cout <<"DFS 后的順序?yàn)?:"<<endl;	DFS_tra (G) ;	cout<< endl;	system ("pause" ) ;	return 0 ;}
通過鄰接表進(jìn)行BFS，我覺得寫得算簡單，雖然寫的很費(fèi)勁
#include<iostream>#include<string>#include<queue>#include<windows.h>using namespace std;#define Max 20  bool visit[20] ;//跟前面無向圖里面的作用一樣，后期用來判斷是否被訪問過 int Vex_Num; //看到網(wǎng)上都有這個，主要是用來判斷是否每個點(diǎn)都訪問過了   struct ArcNode{	int adjvex ; //弧所指的頂點(diǎn)位置  	ArcNode *nextarc ;// 指向next ->弧  } ;    typedef struct VNode{  	string data ;//頂點(diǎn)  	ArcNode *firarc ; //頂點(diǎn)出來的第一條狐  }AdjList [Max] ;    struct HGraph{  	AdjList vertices;//頭結(jié)點(diǎn)數(shù)組  	int vexnum;//頂點(diǎn)數(shù)  	int arcnum;//邊數(shù)  } ;    int Locate(HGraph G,string x){  //定位頂點(diǎn)位置 	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<<"請輸入頂點(diǎn)的數(shù)目和邊的數(shù)目：";  	cin>>G.vexnum>>G.arcnum;  	cout<<"請輸入頂點(diǎn)名稱：";  	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順序輸入邊所對應(yīng)的兩個頂點(diǎn)：" ;  		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) ; //進(jìn)站  				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;  //說明已經(jīng)全部訪問過							if(G.vertices[w].firarc)  									q.push(w);  					}  				}  			}  		}  	}  }//操他媽的覺得圖論好難int main  () {	HGraph G;	Create (G) ;	cout <<"經(jīng)過廣度優(yōu)先遍歷后輸出的順序?yàn)?："<<endl; 	BFS_Tra (G) ;	system ("pause") ;}