图结构的 DFS/BFS 遍历

labuladong原创

前置知识

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

一句话总结

图的遍历就是多叉树遍历的延伸，主要遍历方式还是深度优先搜索（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, visited);  }  // 后序位置 }

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 traverseGraph(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 {  traverseGraph(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);  }  // 后序位置 };

可以看到，图的遍历比多叉树的遍历多了一个 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

// 多叉树节点 class Node { public:  int val;  vector<Node*> children;    Node(int v = 0) : val(v) {} };  // 遍历多叉树的树枝 void traverseBranch(Node* root) {  // base case  if (root == nullptr) {  return;  }  for (Node* child : root->children) {  cout << "visit branch: " << root->val << " -> " << child->val << endl;  traverseBranch(child);  } }  // 图节点 class Vertex { public:  int id;  vector<Vertex*> neighbors;    Vertex(int i = 0) : id(i) {} };  // 遍历图的边 // 需要一个二维 visited 数组记录被遍历过的边，visited[u][v] 表示边 u->v 已经被遍历过 void traverseEdges(Vertex* s, vector<vector<bool>>& visited) {  // base case  if (s == nullptr) {  return;  }  for (Vertex* neighbor : s->neighbors) {  // 如果边已经被遍历过，则跳过  if (visited[s->id][neighbor->id]) {  continue;  }  // 标记并访问边  visited[s->id][neighbor->id] = true;  cout << "visit edge: " << s->id << " -> " << neighbor->id << endl;  traverseEdges(neighbor, visited);  } }

python

# 多叉树节点 class Node:  def __init__(self, val=0, children=None):  self.val = val  self.children = children if children is not None else []  # 遍历多叉树的树枝 def traverse_branch(root):  # base case  if root is None:  return  for child in root.children:  print(f"visit branch: {root.val} -> {child.val}")  traverse_branch(child)  # 图节点 class Vertex:  def __init__(self, id=0, neighbors=None):  self.id = id  self.neighbors = neighbors if neighbors is not None else []  # 遍历图的边 # 需要一个二维 visited 数组记录被遍历过的边，visited[u][v] 表示边 u->v 已经被遍历过 def traverse_edges(s, visited):  # base case  if s is None:  return  for neighbor in s.neighbors:  # 如果边已经被遍历过，则跳过  if visited[s.id][neighbor.id]:  continue  # 标记并访问边  visited[s.id][neighbor.id] = True  print(f"visit edge: {s.id} -> {neighbor.id}")  traverse_edges(neighbor, visited)

package main  import "fmt"  // 多叉树节点 type Node struct {  Val int  Children []*Node }  // 遍历多叉树的树枝 func traverseBranch(root *Node) {  // base case  if root == nil {  return  }  for _, child := range root.Children {  fmt.Printf("visit branch: %d -> %d\n", root.Val, child.Val)  traverseBranch(child)  } }  // 图节点 type Vertex struct {  ID int  Neighbors []*Vertex }  // 遍历图的边 // 需要一个二维 visited 数组记录被遍历过的边，visited[u][v] 表示边 u->v 已经被遍历过 func traverseEdges(s *Vertex, visited [][]bool) {  // base case  if s == nil {  return  }  for _, neighbor := range s.Neighbors {  // 如果边已经被遍历过，则跳过  if visited[s.ID][neighbor.ID] {  continue  }  // 标记并访问边  visited[s.ID][neighbor.ID] = true  fmt.Printf("visit edge: %d -> %d\n", s.ID, neighbor.ID)  traverseEdges(neighbor, visited)  } }

javascript

// 多叉树节点 class Node {  constructor(val = 0, children = []) {  this.val = val;  this.children = children;  } }  // 遍历多叉树的树枝 function traverseBranch(root) {  // base case  if (root === null) {  return;  }  for (let child of root.children) {  console.log(`visit branch: ${root.val} -> ${child.val}`);  traverseBranch(child);  } }  // 图节点 class Vertex {  constructor(id = 0, neighbors = []) {  this.id = id;  this.neighbors = neighbors;  } }  // 遍历图的边 // 需要一个二维 visited 数组记录被遍历过的边，visited[u][v] 表示边 u->v 已经被遍历过 function traverseEdges(s, visited) {  // base case  if (s === null) {  return;  }  for (let neighbor of s.neighbors) {  // 如果边已经被遍历过，则跳过  if (visited[s.id][neighbor.id]) {  continue;  }  // 标记并访问边  visited[s.id][neighbor.id] = true;  console.log(`visit edge: ${s.id} -> ${neighbor.id}`);  traverseEdges(neighbor, 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）

写法一

写法二

写法三