【数据结构】邻接矩阵之深度优先遍历DFS_根据邻接矩阵写出深度优先遍历

以某一顶点为起点，深度遍历，v->w1->w2->.......u

回退一步，看是否有其他未被访问的邻接点 

#include<iostream> 
using namespace std;
#define MaxInt 32767  //表示极大值 
#define MVNum 100  //最大顶点数 
typedef char VerTexType;   //设置顶点类型为字符型 
typedef int ArcType;    //设置权重为整型 
 
typedef struct{
	VerTexType vexs[MVNum];    //顶点表 
	ArcType arcs[MVNum][MVNum];   //邻接矩阵 
	int vexnum,arcnum;  //顶点数和边数 
}AMGraph;
 
从顶点表中查找顶点 
int LocateVex(AMGraph G,VerTexType u){  
	int i;
	for(i=0;i<G.vexnum;i++)
		if(u==G.vexs[i]) return i; 
	return -1;
} 
 
 
//构造无向图
int CreateUDG(AMGraph &G){
	int i,j,k;
	cout<<"请输入顶点数和边数：";
	cin>>G.vexnum>>G.arcnum;
	cout<<"输入顶点：";
	for(i=0;i<G.vexnum;i++) 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++){
		VerTexType v1,v2;
		ArcType w;
		cout<<"输入依附的顶点：";
		cin>>v1>>v2;
		i=LocateVex(G,v1);
		j=LocateVex(G,v2);
		G.arcs[i][j]=1;
		G.arcs[j][i]=G.arcs[i][j];
	}
	return 1;
} 
 
 
//输出邻接矩阵 
void Show(AMGraph G){  
	int i,j;
	for(i=0;i<G.vexnum;i++){
		for(j=0;j<G.vexnum;j++)
			if(G.arcs[i][j]==MaxInt) cout<<"∞"<<' ';
			else cout<<G.arcs[i][j]<<' ';
		cout<<endl;	
		}
 
}
 
bool visited[MVNum];    //辅助数组，标记该结点是否被访问
//深度优先遍历DFS
void DFS(AMGraph G,int v){
	int w;
	cout<<G.vexs[v]; visited[v]=1;      //访问第v个结点
	for(w=0;w<G.vexnum;w++)    //依次检查v所在行
		if(G.arcs[v][w] && !visited[w])  //如果w是邻接点且未被访问，则递归调用DFS
			DFS(G,w);
} 
 
int main(){
	AMGraph G;
	CreateUDG(G);
	cout<<endl<<"构造的无向图为："<<endl;
	Show(G);
	
	int v;
	cout<<endl<<"请输入DFS起点：";
	cin>>v;
	cout<<"深度优先遍历DFS结果为：";
	DFS(G,v);
	return 1;
}

运行结果：