图的深度优先搜索dfs
程序员文章站
2022-06-22 21:49:53
图的深度优先搜索: 1.将最初访问的顶点压入栈; 2.只要栈中仍有顶点,就循环进行下述操作: (1)访问栈顶部的顶点u; (2)从当前访问的顶点u 移动至顶点v 时,将v 压入栈。如果当前顶点u 不存在未访问的相邻矩阵,则将u 从栈中删除; 主要的几个变量: color[n] 用WHITE、GRAY ......
图的深度优先搜索:
1.将最初访问的顶点压入栈;
2.只要栈中仍有顶点,就循环进行下述操作:
(1)访问栈顶部的顶点u;
(2)从当前访问的顶点u 移动至顶点v 时,将v 压入栈。如果当前顶点u 不存在未访问的相邻矩阵,则将u 从栈中删除;
主要的几个变量:
color[n] | 用white、gray、black 中的一个来表示顶点i 的访问状态 |
m[n][n] | 邻接矩阵, 如果存在顶点i 到顶点j 的边,则m[i][j]为true |
stack s |
栈, 暂存访问过程中的顶点 |
其中color 数组中, 白色代表“未访问的顶点”, 灰色代表“访问过的顶点”(虽然被访问过了,但仍然可能留有通往未访问顶点的边), 黑色代表”访问结束的顶点”;
有俩种方法实现深度优先遍历
(1)用递归实现的深度优先搜索
#include<stdio.h> #define n 100 #define white 0 #define gray 1 #define black 2 int n, m[n][n]; int color[n], d[n], f[n], tt;//color[n]表示该顶点访问与否,d[n]表示该顶点的发现时刻 ,f[n]表示该顶点的结束时刻 ,tt表示时间 //用递归函数实现的深度优先搜索 void dfs_visit(int u) { int v; color[u] = gray; d[u] = ++tt; for(v = 0; v < n; v++) { if(m[u][v] == 0) continue; if(color[v] == white) dfs_visit(v); } color[u] = black; f[u] = ++tt;//访问结束 } void dfs() { int u; //初始化 for(u = 0; u < n; u++) color[u] = white; tt = 0; //以未访问的u为起点进行深度优先搜索 for(u = 0; u < n; u++) { if(color[u] == white) dfs_visit(u); } //输出 for(u = 0; u < n; u++) { printf("%d %d %d\n", u+1, d[u], f[u]); } } int main() { int u, v, k, i, j; scanf("%d", &n); //初始化 for(i = 0; i < n; i++) { for(j = 0; j < n; j++) { m[i][j] = 0; } } //输入数据,构造邻接矩阵 for(i = 0; i < n; i++) { scanf("%d %d", &u, &k); u--; for(j = 0; j < k; j++) { scanf("%d", &v); v--; m[u][v] = 1; } } dfs(); return 0; } /* 6 1 2 2 3 2 2 3 4 3 1 5 4 1 6 5 1 6 6 0 */
(2)用栈实现的深度优先搜索
#include<iostream> #include<stack> using namespace std; static const int n = 100; static const int white = 0; static const int gray = 1; static const int black = 2; int n, m[n][n]; int color[n], d[n], f[n], tt;//color[n]表示该顶点访问与否,d[n]表示该顶点的发现时刻 ,f[n]表示该顶点的结束时刻 int nt[n];//记录每个顶点的邻接顶点偏移量,eg:顶点0有俩个顶点1,2;现已经访问过1了,那么, nt[u] = 1; 下次直接访问2 //按编号顺序获取与u相邻的v int next(int u) { for(int v = nt[u]; v < n; v++) { nt[u] = v + 1; if(m[u][v]) return v; } return -1; } void dfs_visit(int r) { for(int i = 0; i < n; i++) nt[i] = 0; stack <int> s; s.push(r); color[r] = gray; d[r] = ++tt; while( !s.empty() ) { int u = s.top(); int v = next(u); if(v != -1) { if(color[v] == white) { color[v] = gray; d[v] = ++tt; s.push(v); } } else { s.pop(); color[u] = black; f[u] = ++tt; } } } void dfs() { //初始化 for( int i = 0; i < n; i++) { color[i] = white; nt[i] = 0; } //设置时间 tt = 0; //以未访问的u为起点进行深度优先搜索,设置循环的目的应该是防止该图不是连通图 for(int u = 0; u < n; u++) { if(color[u] == white) dfs_visit(u); } for(int i = 0; i < n; i++) { cout << i+1 << " " << d[i] << " " << f[i] << endl; } } int main() { int u, k, v; cin >> n; //顶点数 //邻接矩阵置零 for( int i = 0; i < n; i++) { for(int j = 0; j < n; j++) m[i][j] = 0; } //创建邻接矩阵 for(int i = 0; i < n; i++) { cin >> u >> k;//输入顶点和顶点的度 u--; for(int j = 0; j < k; j++) { cin >> v; v--; m[u][v] = 1; } } dfs(); return 0; } /* 6 1 2 2 3 2 2 3 4 3 1 5 4 1 6 5 1 6 6 0 */