欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

用DFS 遍历图

程序员文章站 2022-03-03 11:36:00
...

参考资料:《算法笔记》

思想:

以“深度”作为第一关键词,每次都是沿着路径走到不能再前进了才退回最近的岔路口;

具体实现:

dfs一次能遍历一个连通块,
如果图是连通图,那么一次DFS就能遍历完成所有顶点:

dfs(u){	//访问顶点u
	vis[u] = true;	//设置u已被访问
	for(从u出发的所有能到达的顶点v)
		if(!vis[v]) dfs(v);	//v未被访问就递归访问v
}
dfstrave(g){	//dfs遍历图g
	for(g的所有顶点u)
		if(!vis[u]) dfs(u);	//u未被访问就访问u所在的连通块
}

邻接矩阵实现:

int n, g[maxn][maxn];
bool vis[maxn] = {false};

void dfs(int u, int depth){
	vis[u] = true;	//访问u 
	//如果要对u进行操作,在这里进行
	//下面对u能到达的分支顶点进行枚举
	for(int v = 0; v < n; v++){
		if(!vis[v] && g[u][v] != INF){	//v未访问且可达 
			dfs(v, depth + 1);	//访问v,深度+1			
		}
	} 
}

int main(){ 
	
	.......
	//遍历图g 
	for(int u = 0; u < n; u ++){
		if(!vis[u])	//如果u未访问 
			dfs(u, 1);	//访问u所在的连通块 
	} 
	......
} 

邻接表实现:

int n;
vector<int> adj[maxn]; 
bool vis[maxn] = {false};

void dfs(int u, int depth){
	vis[u] = true;	//访问u 
	//如果要对u进行操作,在这里进行
	//下面对u能到达的分支顶点进行枚举
	for(int i = 0; i < adj[u].size(); i++){
		int v = adj[u][i];
		if(!vis[v]){	//v未访问
			dfs(v, depth + 1);	//访问v,深度+1			
		}
	} 
}

int main(){ 
	
	.......
	//遍历图g 
	for(int u = 0; u < n; u ++){
		if(!vis[u])	//如果u未访问 
			dfs(u, 1);	//访问u所在的连通块 
	} 
	...... 
} 

PAT 相关题目:

PAT 1034 Head of a Gang (30分)