图的DFS（邻接矩阵版、邻接表版）

Rohana ·

更新时间:2024-09-21

· 527 次阅读

先上伪码，思路写的比较清楚：
伪代码:


DFS(u){             //访问顶点u
	vis[u] = true;   //设置u已被访问 
	for(从u出发能到达的所有顶点v){   //枚举从u出发可以到达的所有顶点v 
		if vis[v] == false           //如果v未被访问 
		DFS(v)            //递归访问v 
	}
} 
DFSTrave(G){       //遍历图 
	for(G的所有顶点){     //对G的所有顶点u 
		if vis[u] == false    //如果u未被访问 
		DFS(u)    //访问u所在的连通块 
	}
}

1、邻接矩阵版：


const int MAXV = 1000;     //最大顶点数 
const int INF = 100000000;  //设INF为一个很大的数 
int n,G[MAXV][MAXV];       //n为顶点数 
bool vis[MAXV] = {false};
void DFS(int u,int depth){    //u为当前访问的顶点标号，depth为深度 
	vis[u] = true;
	//如果需要对u进行一些操作，可以在这里进行 
	//下面对所有从u出发能到达的分支顶点进行枚举 
	for(int v = 0;v <n;v++){    //对每个顶点v 
		if(vis[v] == false && G[u][v] != INF){     //如果v未被访问，且u可达到v 
			DFS(v,depth+1);    //访问v，深度+1（depth这里有什么用？） 
		}
	}
}
void DFSTrave(){   //遍历图G 
	for(int u = 0;u <n;u++){   //对每个顶点u 
		if(vis[u] == false){   //如果u未被访问 
			DFS(u,1);         //访问u和u所在的连通块，1表示初始为第一层 
		}
	}
}

2、邻接表版


const int MAXV = 1000;     //最大顶点数 
const int INF = 100000000;  //设INF为一个很大的数 
vector Adj[MAXV];
int n;
bool vis[MAXV] = {false};
void DFS(int u,int depth){
	vis[u] = true;
	//如果需要对u进行一些操作，可以在此处进行
	for(int i = 0;i <Adj[u].size();i++){
		int v = Adj[u][i];
		if(vis[v] == false){
			DFS(v,depth+1);
		}
	} 
}
void DFSTrave(){
	for(int u = 0;u <n;u++){
		if(vis[u] == false){
			DFS(u,1);
		}
	}
}

作者：晴空_万里

邻接矩阵邻接表 dfs 矩阵

1024 个赞