图结构的 DFS/BFS 遍历

labuladong原创约 4927 字

前置知识

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

一句话总结

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

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

遍历图的「节点」和「路径」略有不同，遍历「节点」时，需要 visited 数组在前序位置标记节点；遍历图的所有「路径」时，需要 onPath 数组在前序位置标记节点，在后序位置撤销标记。

可视化面板支持创建图结构，同时支持可视化 DFS/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, visited):
    # base case
    if s is None:
        return
    if visited.get(s.id, False):
        # 防止死循环
        return
    # 前序位置
    visited[s.id] = True
    print(f"visit {s.id}")
    for neighbor in s.neighbors:
        traverse_graph(neighbor)
    # 后序位置

go 🤖

// 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)
    # 后序位置

go 🤖

// 遍历图的所有节点
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);
    }
    // 后序位置
};

由于 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)$ 。

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

对于树结构，遍历所有「路径」和遍历所有「节点」是没什么区别的。而对于图结构，遍历所有「路径」和遍历所有「节点」稍有不同。

因为对于树结构来说，只能由父节点指向子节点，所以从根节点 root 出发，到任意一个节点 targetNode 的路径都是唯一的。换句话说，我遍历一遍树结构的所有节点之后，必然可以找到 root 到 targetNode 的唯一路径：

图结构的 DFS/BFS 遍历

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

797. All Paths From Source to Target https://leetcode.com/problems/all-paths-from-source-to-target

深度优先搜索（DFS）

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

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

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

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

广度优先搜索（BFS）

写法一

写法二

写法三

图结构的 DFS/BFS 遍历

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

797. All Paths From Source to Target https://leetcode.com/problems/all-paths-from-source-to-target

深度优先搜索（DFS）

遍历所有节点（visited 数组）

遍历所有路径（onPath 数组）

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

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

广度优先搜索（BFS）

写法一

写法二

写法三

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

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