图论-DFS/BFS

图论-DFS/BFS

参考资料: DFS（图论） - OI Wiki

深度优先搜索DFS

引入

​ 深度优先搜索 (Depth First Search)，简称 深搜 或者 DFS，是一种用于遍历或搜索树或图的算法。顾名思义，深搜就是每次向着下一层次的搜索。

​ 与之相对的是 BFS , 但两者除了遍历图的连通块以外，用途完全不同。

过程

​ DFS 最关键的地方就是通过栈实现 “回退” 至上一结点以遍历同一层次的结点，我们也可以通过递归实现(这是主流用法)，毕竟递归是依靠栈实现的。访问每个结点时得为其打上标记，避免重复访问。

​ 显然我们可以得到这样一个DFS结构

1
2
3
4
5
6
7
dfs(v){//v为图中的一个顶点，有时也可以是其他抽象的概念，如dp状态
	//标记v    
    for u in v相邻的结点{
    	if 如果u没有标记
    	dfs(u) //递归访问u结点
    }
}

性质

​ 该算法通常的时间复杂度为 \(O(n+m)\) ，空间复杂度为 \(O(n)\), 其中 \(n\) 表示点数，\(m\) 表示边数。在平均 \(O(1)\) 遍历一条边的条件下才能到达这个时间复杂度，例如用前向星和邻接表存储图。

实现

这里假设使用邻接表存储图

递归实现(常用)

1
2
3
4
5
6
7
8
9
10
11
vector<vector<int>> g; //邻接表
vector<bool> visited; //标记结点是否被遍历过

void dfs(int u){ //从u开始遍历图的连通块
    visited[u] = true;
    for(int i:g[u]){
        if(!visited[i]){
            dfs(i);
        }
    }
}

栈实现

以下代码来自OI Wiki

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<vector<int>> adj;  // 邻接表
vector<bool> vis;         // 记录节点是否已经遍历

void dfs(int s) {
  stack<int> st;
  st.push(s);
  vis[s] = true;

  while (!st.empty()) {
    int u = st.top();
    st.pop();

    for (int v : adj[u]) {
      if (!vis[v]) {
        vis[v] = true;  // 确保栈里没有重复元素
        st.push(v);
      }
    }
  }
}

广度优先搜索BFS

引入

​ 广度优先搜索 (Breadth First Search)，又称宽度优先搜索，一般简称 宽搜 或者BFS 。BFS追求先遍历完所有子结点，再去遍历子节点的子结点，即每次先访问完同一层的结点。显然，BFS 所找到的路径一定是最短的路径 (此处最短指含边最少) 。 BFS一般用 队列 实现。

实现

​ 将子结点(最开始是根结点)先放入队列，在通过队列全部访问，中途也会访问到子结点的子节点，这时将它们队列，那么当子节点那一层访问完毕时，我们就可以开始访问子节点的子节点了(相对的下一层)。当队列为空时，BFS结束。

先给出伪代码，理解BFS的实现过程，这方式和DFS栈的实现方法类似。

以下代码均基于OI Wiki

1
2
3
4
5
6
7
8
9
10
11
12
13
bfs(s) {
  q = new queue() //创建队列
  q.push(s), visited[s] = true //放入当前元素并标记
  while (!q.empty()) {
    u = q.pop() //取出队列元素
    for each edge(u, v) { //遍历基于u的边
      if (!visited[v]) {
      	visited[v] = true	
        q.push(v) //放入队列
      }
    }
  }
}

C++中基于链式前向星的存图方式的BFS实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void bfs(int u) {
  while (!Q.empty()) Q.pop(); //清空队列，以作下用
  Q.push(u); //放入结点u
  vis[u] = 1; //标记u
  d[u] = 0; //用以记录最短距离，视情况用
  p[u] = -1; //记录是从哪个节点走到当前节点的
  while (!Q.empty()) {
    u = Q.front(); //得到队首u
    Q.pop();
    for (int i = head[u]; i; i = e[i].nxt) { //访问连接u的边
      if (!vis[e[i].to]) {
        Q.push(e[i].to); //放入队列
        vis[e[i].to] = 1;
        d[e[i].to] = d[u] + 1; //显然多一条边，距离就+1
        p[e[i].to] = u; //途径此边
      }
    }
  }
}


void restore(int x) {
  vector<int> res;
  for (int v = x; v != -1; v = p[v]) {
    res.push_back(v);
  }
  std::reverse(res.begin(), res.end());
  for (int i = 0; i < res.size(); ++i) printf("%d", res[i]);
  puts("");
}