用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 相关题目:
上一篇: STK解析---菜单点击处理流程
下一篇: 图的遍历dfs