首页 计算机 算法与数据结构 图算法

图的搜索和遍历算法，即 BFS 和 DFS.

# 图的遍历

图的遍历是图的基本问题。其指的是如何通过某个特定的顺序或规则，完成对图中所有点的访问。更具体些，对一个图G(V,E)G(V,E), 我们通常给出图上的一个源点 (source)ss, 如何从ss 出发到达每一个点是我们关注的问题。我们希望得到一种通用的遍历规则。

关于此，我们常有两种方法，分别称为广度优先搜索 (breadth-first search, BFS) 和深度优先搜索 (depth-firth search, DFS)。图算法中的很多想法都源自这两种基本的图遍历方法。

# 广度优先搜索 (BFS)

# 算法代码和思路

我们用一个队列 Q 来记录要处理的节点，然后开一个布尔数组 vis[] 来标记是否已经访问过某个节点。

开始的时候，我们将所有节点的 vis 值设为 0 , 表示没有访问过；然后把起点 s 放入队列 Q 中并将 vis[s] 设为 1 .

之后，我们每次从队列 Q 中取出队首的节点 u , 然后把与 u 相邻的所有节点 v 标记为已访问过并放入队列 Q .

循环直至当队列 Q 为空，表示 BFS 结束。

下面给出广度优先搜索的代码：

BFS(G,s)
void bfs(int u) {
  while (!Q.empty()) Q.pop();
  Q.push(u);
  vis[u] = 1;
  d[u] = 0;
  p[u] = -1;
  while (!Q.empty()) {
    u = Q.front();
    Q.pop();
    for (int i = head[u]; i; i = e[i].nxt) {
      if (!vis[e[i].to]) {
        Q.push(e[i].to);
        vis[e[i].to] = 1;
        d[e[i].to] = d[u] + 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("");
}
# 性质
# 复杂度
  • 时间复杂度：O(n+m)O(n+m).
  • 空间复杂度：O(n)O(n).
# 深度优先搜索
# 算法描述
对最新发现的顶点，如果存在以其为起点但未探测到的边，就继续探测下去。当所有顶点都被探索后，就按照发现该顶点的顺序进行回溯，直到某个顶点存在新的为探测到的边。直到所有的顶点都被探测之后，算法停止。这样的算法称为深度优先搜索 (depth-first search, DFS)。
在深度优先搜索中，每次扫描顶点 uu 的邻接表发现新顶点 vv 时，将 vv 的前辈 π[v]\pi[v] 取 uu. 这样，所有顶点的先辈子图形成一个森林，称为深度优先林 (depth-first forest). 深度优先林中的每一棵树称为深度优先树 (depth-first tree).
此外，在深度优先搜索中，我们在搜索过程中为每个顶点加两个时间戳。当发现一个顶点 vv (将顶点 vv 置灰色) 时，为其添加时间戳 d[v]d[v]. 当结束检查 vv 的邻接表 (将顶点 vv 置黑色) 时，为其添加时间戳 f[v]f[v]. 这样的时间戳为深度优先搜索的拓展起了很大的作用。
下面，我们采用代码表示深度优先搜索的过程：
DFS(G)
// initialize
for (Vertex u : G) {
  u.color = WHITE;
  u.pi = null;
}
int time = 0;
for (Vertex u : G) {
  if (u.color == WHITE) {
    dfs_visit(u);
  }
}
void dfs_visit(Vertex u) {
  u.color = GRAY;
  u.d = ++time; // discovered time
  for (Vertex v : u.adj) { // vertex in u's adjacent nodes
    if (v.color == WHITE) {
      v.pi = u;
      dfs_visit(v);
    }
  }
  u.color = black;
  u.f = ++time; // finished time
}
注意到，我们维护的域越多，可以得到的（冗余）信息也就越多。如果只是单纯进行图遍历，那么发现和完成时刻是不需要维护的。由此，我们可以写一个简单的 DFS. (就是一个迭代)
DFS-simplified
struct vertex {
  int index;
  int label; // if visited
  vector<vertex*> adj;
};
void dfs(vertex* root) {
  // do something
  for (auto v : root) {
    if (v.label == 0) dfs(v);
  }
}
# 性质
# 复杂度
  • 时间复杂度：O(n+m)O(n+m).
  • 空间复杂度：O(n)O(n).
# 括号定理
# 白色路径定理
在一个图G(V,E)G(V,E) 的深度优先森林中，顶点vv 是顶点uu 的后裔，当且仅当搜索过程中于时刻d[u]d[u] 发现uu 时，可以从顶点uu 出发，经过一条完全由白色顶点组成的路径到达vv.
# 深度优先林中边的分类
在深度优先林中，我们对反向边进行分类。可以分为以下四种：
  1. 树边 (tree edge):
  2. 后向边 (back edge)
  3. 前向边
  4. 交叉边
# 应用
  • 连通性判断
  • 判环
  • 拓扑排序
# DAG & 拓扑排序
# DAG
有向无环图 (directed acyclic graph, DAG).
# 拓扑排序
采用 DFS 实现。返回时间的倒序就是一个可行的拓扑序。
# 强连通性
# 强连通图
# Kosaraju 算法
是一个在线性时间 O(n+m)O(n+m) 内寻找一个有向图中的强连通分量的算法。
算法如下：
  1. 对图中的每个顶点 uu, 标记 vis[u] = 0 (unvisited). 同时创建一个存放顶点的空栈 L .
  2. 对图中的每个顶点 uu, 执行 visit(u) , 其中 visit(u) 定义如下：
    void visit(Vertex u) {
      if (vis[u] == 0) {
        vis[u] = 1; // visited
        for (Vertex v : u.outNeighbor) visit(v);
        L.push(u);
      }
    }
  3. 对 L 中的每个顶点 uu, 执行 assign(u, u) ,
For each vertex u of the graph, mark u as unvisited. Let L be empty.
For each vertex u of the graph do Visit(u), where Visit(u) is the recursive subroutine:
If u is unvisited then:
Mark u as visited.
For each out-neighbour v of u, do Visit(v).
Prepend u to L.
Otherwise do nothing.
For each element u of L in order, do Assign(u,u) where Assign(u,root) is the recursive subroutine:
If u has not been assigned to a component then:
Assign u as belonging to the component whose root is root.
For each in-neighbour v of u, do Assign(v,root).
Otherwise do nothing.
# Tarjan 算法
此处的 Tarjan 算法是求强连通分量的 Tarjan 算法。
Tarjan 算法的核心是维护两个标志量：
  • dfn[u] : 表示 DFS 中进入节点 u 的时刻。
  • low[u] : 表示 DFS 中， u 的子树中能够回溯到的最早的已经在栈中的结点，即 dfn 值最小的返祖边指向的点。
于是，从根开始的一条路径上的 dfn 严格递增， low 严格非降。
void TarjanSearch(int u) {
  vis[u] = true;
  low[u] = dfn[u] = ++dfncnt;
  visStack.push(u);
  for(int v=0;v<n;v++) {
    if (edge[u][v] == 1) {
      if (!vis[v]) {
        TarjanSearch(v); // 搜索
        low[u]=min(low[u],low[v]); // 回溯
      }
      else if (visStack.has(v))
        low[u]=min(low[u],dfn[v]);
    }
  }
}
若存在 dfn[u] == low[u] , 那么 u 及其上方的节点 (直到 u 本身) 构成一个强连通分支。