图结构的 DFS/BFS 遍历

labuladong原创约 5902 字

前置知识

阅读本文前，你需要先学习：

一句话总结

图的遍历就是多叉树遍历的延伸，主要遍历方式还是深度优先搜索（DFS）和广度优先搜索（BFS）。

唯一的区别是，树结构中不存在环，而图结构中可能存在环，所以我们需要标记遍历过的节点，避免遍历函数在环中死循环。

由于图结构的复杂性，可以细分为遍历图的「节点」、「边」和「路径」三种场景，每种场景的代码实现略有不同。

遍历图的「节点」和「边」时，需要 visited 数组在前序位置做标记，避免重复遍历；遍历图的「路径」时，需要 onPath 数组在前序位置标记节点，在后序位置撤销标记。

可视化面板支持创建图结构，同时支持可视化 DFS/BFS 遍历的路径。你可以直观地看到，图结构看起来虽然比树结构复杂，但图的遍历本质上还是树的遍历。

先看 DFS 算法，你可以打开下面的可视化面板，多次点击 console.log 这行代码，即可看到 DFS 遍历图的过程，traverse 函数本质上在遍历一棵多叉递归树：

算法可视化面板

再看 BFS 算法，你可以打开下面的可视化面板，多次点击 console.log 这行代码，即可看到 BFS 遍历图的过程，本质上是在层序遍历一棵多叉树：

算法可视化面板

下面具体讲解。

深度优先搜索（DFS）

前文图结构基础和通用实现中说了，我们一般不用 Vertex 这样的类来存储图，但是这里我还是先用一下这个类，以便大家把图的遍历和多叉树的遍历做对比。后面我会给出基于邻接表/邻接矩阵的遍历代码。

遍历所有节点（`visited` 数组）

对比多叉树的遍历框架看图的遍历框架吧：

java

// 多叉树节点
class Node {
    int val;
    List<Node> children;
}

// 多叉树的遍历框架
void traverse(Node root) {
    // base case
    if (root == null) {
        return;
    }
    // 前序位置
    System.out.println("visit " + root.val);
    for (Node child : root.children) {
        traverse(child);
    }
    // 后序位置
}


// 图节点
class Vertex {
    int id;
    Vertex[] neighbors;
}

// 图的遍历框架
// 需要一个 visited 数组记录被遍历过的节点
// 避免走回头路陷入死循环
void traverse(Vertex s, boolean[] visited) {
    // base case
    if (s == null) {
        return;
    }
    if (visited[s.id]) {
        // 防止死循环
        return;
    }
    // 前序位置
    visited[s.id] = true;
    System.out.println("visit " + s.id);
    for (Vertex neighbor : s.neighbors) {
        traverse(neighbor, visited);
    }
    // 后序位置
}

cpp

// 多叉树节点
class Node {
public:
    int val;
    std::vector<Node*> children;
};

// 多叉树的遍历框架
void traverse(Node* root) {
    // base case
    if (root == nullptr) {
        return;
    }
    // 前序位置
    std::cout << "visit " << root->val << std::endl;
    for (auto child : root->children) {
        traverse(child);
    }
    // 后序位置
}

// 图节点
class Vertex {
public:
    int id;
    std::vector<Vertex*> neighbors;
};

// 图的遍历框架
// 需要一个 visited 数组记录被遍历过的节点
// 避免走回头路陷入死循环
void traverse(Vertex* s, std::vector<bool>& visited) {
    // base case
    if (s == nullptr) {
        return;
    }
    if (visited[s->id]) {
        // 防止死循环
        return;
    }
    // 前序位置
    visited[s->id] = true;
    std::cout << "visit " << s->id << std::endl;
    for (auto neighbor : s->neighbors) {
        traverse(neighbor);
    }
    // 后序位置
}

python

# 多叉树节点
class Node:
    def __init__(self, val=0, children=None):
        self.val = val
        self.children = children if children is not None else []

# 多叉树的遍历框架
def traverse(root):
    # base case
    if root is None:
        return
    # 前序位置
    print(f"visit {root.val}")
    for child in root.children:
        traverse(child)
    # 后序位置

# 图节点
class Vertex:
    def __init__(self, id=0, neighbors=None):
        self.id = id
        self.neighbors = neighbors if neighbors is not None else []

# 图的遍历框架
# 需要一个 visited 数组记录被遍历过的节点
# 避免走回头路陷入死循环
def traverse_graph(s: Vertex, visited: List[bool]):
    # base case
    if s is None:
        return
    if visited[s.id]:
        # 防止死循环
        return
    # 前序位置
    visited[s.id] = True
    print(f"visit {s.id}")
    for neighbor in s.neighbors:
        traverse_graph(neighbor, visited)
    # 后序位置

// Node 多叉树节点
type Node struct {
    val      int
    children []*Node
}

// 多叉树的遍历框架
func traverse(root *Node) {
    // base case
    if root == nil {
        return
    }
    // 前序位置
    fmt.Println("visit", root.val)
    for _, child := range root.children {
        traverse(child)
    }
    // 后序位置
}

// Vertex 图节点
type Vertex struct {
    id        int
    neighbors []*Vertex
}


// 图的遍历框架
// 需要一个 visited 数组记录被遍历过的节点
// 避免走回头路陷入死循环
func traverse(s *Vertex, visited []bool) {
    // base case
    if s == nil {
        return
    }
    if visited[s.id] {
        // 防止死循环
        return
    }
    // 前序位置
    visited[s.id] = true
    fmt.Println("visit", s.id)
    for _, neighbor := range s.neighbors {
        traverse(neighbor, visited)
    }
    // 后序位置
}

javascript

// 多叉树节点
class Node {
    constructor(val) {
        this.val = val;
        this.children = [];
    }
}

// 多叉树的遍历框架
var traverseTree = function(root) {
    // base case
    if (root === null) {
        return;
    }
    // 前序位置
    console.log("visit " + root.val);
    for (var i = 0; i < root.children.length; i++) {
        traverseTree(root.children[i]);
    }
    // 后序位置
};

// 图节点
class Vertex {
    constructor(id) {
        this.id = id;
        this.neighbors = [];
    }
}

// 图的遍历框架
// 需要一个 visited 数组记录被遍历过的节点
// 避免走回头路陷入死循环
var traverseGraph = function(s, visited) {
    // base case
    if (s === null) {
        return;
    }
    if (visited[s.id]) {
        // 防止死循环
        return;
    }
    // 前序位置
    visited[s.id] = true;
    console.log("visit " + s.id);
    for (var i = 0; i < s.neighbors.length; i++) {
        traverseGraph(s.neighbors[i]);
    }
    // 后序位置
};

可以看到，图的遍历比多叉树的遍历多了一个 visited 数组，用来记录被遍历过的节点，避免遇到环时陷入死循环。

为什么成环会导致死循环

举个最简单的成环场景，有一条 1 -> 2 的边，同时有一条 2 -> 1 的边，节点 1, 2 就形成了一个环：

1 <=> 2

如果我们不标记遍历过的节点，那么从 1 开始遍历，会走到 2，再走到 1，再走到 2，再走到 1，如此 1->2->1->2->... 无限递归循环下去。

如果有了 visited 数组，第一次遍历到 1 时，会标记 1 为已访问，出现 1->2->1 这种情况时，发现 1 已经被访问过，就会直接返回，从而终止递归，避免了死循环。

有了上面的铺垫，就可以写出基于邻接表/邻接矩阵的图遍历代码了。虽然邻接表/邻接矩阵的底层存储方式不同，但提供了统一的 API，所以直接使用图结构基础和通用实现中那个 Graph 接口的方法即可：

java

// 遍历图的所有节点
void traverse(Graph graph, int s, boolean[] visited) {
    // base case
    if (s < 0 || s >= graph.size()) {
        return;
    }
    if (visited[s]) {
        // 防止死循环
        return;
    }
    // 前序位置
    visited[s] = true;
    System.out.println("visit " + s);
    for (Edge e : graph.neighbors(s)) {
        traverse(graph, e.to, visited);
    }
    // 后序位置
}

cpp

// 遍历图的所有节点
void traverse(const Graph& graph, int s, std::vector<bool>& visited) {
    // base case
    if (s < 0 || s >= graph.size()) {
        return;
    }
    if (visited[s]) {
        // 防止死循环
        return;
    }
    // 前序位置
    visited[s] = true;
    std::cout << "visit " << s << std::endl;
    for (const Graph::Edge& e : graph.neighbors(s)) {
        traverse(graph, e.to, visited);
    }
    // 后序位置
}

python

# 遍历图的所有节点
def traverse(graph, s, visited):
    # base case
    if s < 0 or s >= len(graph):
        return
    if visited[s]:
        # 防止死循环
        return
    # 前序位置
    visited[s] = True
    print("visit", s)
    for e in graph.neighbors(s):
        traverse(graph, e.to, visited)
    # 后序位置

// 遍历图的所有节点
func traverse(graph Graph, s int, visited []bool) {
    // base case
    if s < 0 || s >= len(graph) {
        return
    }
    if visited[s] {
        // 防止死循环
        return
    }
    // 前序位置
    visited[s] = true
    fmt.Println("visit", s)
    for _, e := range graph.neighbors(s) {
        traverse(graph, e.to, visited)
    }
    // 后序位置
}

javascript

// 遍历图的所有节点
var traverse = function(graph, s, visited) {
    // base case
    if (s < 0 || s >= graph.size()) {
        return;
    }
    if (visited[s]) {
        // 防止死循环
        return;
    }
    // 前序位置
    visited[s] = true;
    console.log("visit " + s);
    for (var e of graph.neighbors(s)) {
        traverse(graph, e.to, visited);
    }
    // 后序位置
};

你可以打开下面的可视化面板，多次点击 console.log 这行代码，即可看到 DFS 遍历图的过程：

算法可视化面板

由于 visited 数组的剪枝作用，这个遍历函数会遍历一次图中的所有节点，并尝试遍历一次所有边，所以算法的时间复杂度是 $O(E + V)$ ，其中 E 是边的总数，V 是节点的总数。

时间复杂度为什么是 $O(E + V)$ ？

我们之前讲解二叉树的遍历时说，二叉树的遍历函数时间复杂度是 $O(N)$ ，其中 $N$ 是节点的总数。

这里图结构既然是树结构的延伸，为什么图的遍历函数时间复杂度是 $O(E + V)$ ，要把边的数量 $E$ 也算进去呢？为什么不是 $O(V)$ 呢？

这是个非常好的问题。你可以花上两分钟想想，我把答案写在下面。

点击查看答案

其实二叉树/多叉树的遍历函数，也要算上边的数量，只不过对于树结构来说，边的数量和节点的数量是近似相等的，所以时间复杂度还是 $O(N + N) = O(N)$ 。

树结构中的边只能由父节点指向子节点，所以除了根节点，你可以把每个节点和它上面那条来自父节点的边配成一对儿，这样就可以比较直观地看出边的数量和节点的数量是近似相等的。

而对于图结构来说，任意两个节点之间都可以连接一条边，边的数量和节点的数量不再有特定的关系，所以我们要说图的遍历函数时间复杂度是 $O(E + V)$ 。

遍历所有边（二维 `visited` 数组）

对于图结构，遍历所有边的场景并不多见，主要是计算欧拉路径时会用到，所以这里简单提一下。

上面遍历所有节点的代码用一个一维的 visited 数组记录已经访问过的节点，确保每个节点只被遍历一次；那么最简单直接的实现思路就是用一个二维的 visited 数组来记录遍历过的边（visited[u][v] 表示边 u->v 已经被遍历过），从而确保每条边只被遍历一次。

先参考多叉树的遍历进行对比：

java

// 多叉树节点
class Node {
    int val;
    List<Node> children;
}

// 遍历多叉树的树枝
void traverseBranch(Node root) {
    // base case
    if (root == null) {
        return;
    }
    for (Node child : root.children) {
        System.out.println("visit branch: " + root.val + " -> " + child.val);
        traverseBranch(child);
    }
}

// 图节点
class Vertex {
    int id;
    Vertex[] neighbors;
}

// 遍历图的边
// 需要一个二维 visited 数组记录被遍历过的边，visited[u][v] 表示边 u->v 已经被遍历过
void traverseEdges(Vertex s, boolean[][] visited) {
    // base case
    if (s == null) {
        return;
    }
    for (Vertex neighbor : s.neighbors) {
      // 如果边已经被遍历过，则跳过
      if (visited[s.id][neighbor.id]) {
        continue;
      }
      // 标记并访问边
      visited[s.id][neighbor.id] = true;
      System.out.println("visit edge: " + s.id + " -> " + neighbor.id);
      traverseEdges(neighbor, visited);
    }
}

cpp

// 从起点 s 开始遍历图的所有边
void traverseEdges(const Graph& graph, int s, std::vector<std::vector<bool>>& visited) {
    // base case
    if (s < 0 || s >= graph.size()) {
        return;
    }
    for (const Graph::Edge& e : graph.neighbors(s)) {
        // 如果边已经被遍历过，则跳过
        if (visited[s][e.to]) {
            continue;
        }
        // 标记并访问边
        visited[s][e.to] = true;
        std::cout << "visit edge: " << s << " -> " << e.to << std::endl;
        traverseEdges(graph, e.to, visited);
    }
}

python

# 从起点 s 开始遍历图的所有边
def traverse_edges(graph, s, visited):
    # base case
    if s < 0 or s >= len(graph):
        return
    for e in graph.neighbors(s):
        # 如果边已经被遍历过，则跳过
        if visited[s][e.to]:
            continue
        # 标记并访问边
        visited[s][e.to] = True
        print(f"visit edge: {s} -> {e.to}")
        traverse_edges(graph, e.to, visited)

// 从起点 s 开始遍历图的所有边
func traverseEdges(graph Graph, s int, visited [][]bool) {
    // base case
    if s < 0 || s >= len(graph) {
        return
    }
    for _, e := range graph.neighbors(s) {
        // 如果边已经被遍历过，则跳过
        if visited[s][e.to] {
            continue
        }
        // 标记并访问边
        visited[s][e.to] = true
        fmt.Printf("visit edge: %d -> %d\n", s, e.to)
        traverseEdges(graph, e.to, visited)
    }
}

javascript

// 从起点 s 开始遍历图的所有边
var traverseEdges = function(graph, s, visited) {
    // base case
    if (s < 0 || s >= graph.size()) {
        return;
    }
    var neighbors = graph.neighbors(s);
    for (var i = 0; i < neighbors.length; i++) {
        var e = neighbors[i];
        // 如果边已经被遍历过，则跳过
        if (visited[s][e.to]) {
            continue;
        }
        // 标记并访问边
        visited[s][e.to] = true;
        console.log("visit edge: " + s + " -> " + e.to);
        traverseEdges(graph, e.to, visited);
    }
};

提示

由于一条边由两个节点构成，所以我们需要把前序位置的相关代码放到 for 循环内部。

接下来，我们可以用图结构基础和通用实现中的 Graph 接口来实现：

java

// 从起点 s 开始遍历图的所有边
void traverseEdges(Graph graph, int s, boolean[][] visited) {
    // base case
    if (s < 0 || s >= graph.size()) {
        return;
    }
    for (Edge e : graph.neighbors(s)) {
      // 如果边已经被遍历过，则跳过
      if (visited[s][e.to]) {
        continue;
      }
      // 标记并访问边
      visited[s][e.to] = true;
      System.out.println("visit edge: " + s + " -> " + e.to);
      traverseEdges(graph, e.to, visited);
    }
}

cpp

// 从起点 s 开始遍历图的所有边
void traverseEdges(const Graph& graph, int s, std::vector<std::vector<bool>>& visited) {
    // base case
    if (s < 0 || s >= graph.size()) {
        return;
    }
    for (const Graph::Edge& e : graph.neighbors(s)) {
      // 如果边已经被遍历过，则跳过
      if (visited[s][e.to]) {
        continue;
      }
      // 标记并访问边
      visited[s][e.to] = true;
      std::cout << "visit edge: " << s << " -> " << e.to << std::endl;
      traverseEdges(graph, e.to, visited);
    }
}

python

# 从起点 s 开始遍历图的所有边
def traverse_edges(graph, s, visited):
    # base case
    if s < 0 or s >= len(graph):
        return
    for e in graph.neighbors(s):
        # 如果边已经被遍历过，则跳过
        if visited[s][e.to]:
            continue
        # 标记并访问边
        visited[s][e.to] = True
        print(f"visit edge: {s} -> {e.to}")
        traverse_edges(graph, e.to, visited)

// 从起点 s 开始遍历图的所有边
func traverseEdges(graph Graph, s int, visited [][]bool) {
    // base case
    if s < 0 || s >= len(graph) {
        return
    }
    for _, e := range graph.neighbors(s) {
        // 如果边已经被遍历过，则跳过
        if visited[s][e.to] {
            continue
        }
        // 标记并访问边
        visited[s][e.to] = true
        fmt.Printf("visit edge: %d -> %d\n", s, e.to)
        traverseEdges(graph, e.to, visited)
    }
}

javascript

// 从起点 s 开始遍历图的所有边
var traverseEdges = function(graph, s, visited) {
    // base case
    if (s < 0 || s >= graph.size()) {
        return;
    }
    var neighbors = graph.neighbors(s);
    for (var i = 0; i < neighbors.length; i++) {
        var e = neighbors[i];
        // 如果边已经被遍历过，则跳过
        if (visited[s][e.to]) {
            continue;
        }
        // 标记并访问边
        visited[s][e.to] = true;
        console.log("visit edge: " + s + " -> " + e.to);
        traverseEdges(graph, e.to, visited);
    }
};

显然，使用二维 visited 数组并不是一个很高效的实现方式，因为需要创建二维 visited 数组，这个算法的时间复杂度是 $O(E + V^2)$ ，空间复杂度是 $O(V^2)$ ，其中 $E$ 是边的数量， $V$ 是节点的数量。

在讲解 Hierholzer 算法计算欧拉路径时，我们会介绍一种简单的优化避免使用二维 visited 数组，这里暂不展开。

图结构的 DFS/BFS 遍历

797. 所有可能的路径 https://leetcode.cn/problems/all-paths-from-source-to-target

深度优先搜索（DFS）

遍历所有节点（`visited` 数组）

遍历所有边（二维 `visited` 数组）

遍历所有路径（`onPath` 数组）

同时使用 `visited` 和 `onPath` 数组

完全不用 `visited` 和 `onPath` 数组

广度优先搜索（BFS）

写法一

写法二

写法三