跳转至

9.3   图的遍历

树代表的是“一对多”的关系,而图则具有更高的自由度,可以表示任意的“多对多”关系。因此,我们可以把树看作图的一种特例。显然,树的遍历操作也是图的遍历操作的一种特例。

图和树都需要应用搜索算法来实现遍历操作。图的遍历方式也可分为两种:广度优先遍历和深度优先遍历。

9.3.1   广度优先遍历

广度优先遍历是一种由近及远的遍历方式,从某个节点出发,始终优先访问距离最近的顶点,并一层层向外扩张。如图 9-9 所示,从左上角顶点出发,首先遍历该顶点的所有邻接顶点,然后遍历下一个顶点的所有邻接顶点,以此类推,直至所有顶点访问完毕。

图 9-9   图的广度优先遍历

图解 9-9:图的广度优先遍历:概览

从左上角起点 0 出发,按到起点的最少边数由近及远逐层访问顶点。

待遍历的无向图有 9 个顶点,编号为 0 至 8,按三行三列网格排列:三行依次为 0、1、2;3、4、5;6、7、8。图中只在水平或竖直相邻的顶点之间连接无向边,共 12 条边,没有对角边;各顶点的邻居列在邻接表中。

原图的邻接关系,共十二条无向边
顶点相邻顶点
01、3
10、2、4
21、5
30、4、6
41、3、5、7
52、4、8
63、7
74、6、8
85、7

本图只汇总访问次序,没有画队列或 visited 容器。蓝色虚线箭头表示访问先后,不是原图中的边;例如 1→3、6→5 之间并无原边。灰色曲虚线分隔距起点的不同层,具体成员见下表。完整访问序列为 [0, 1, 3, 2, 4, 6, 5, 7, 8]。

距起点 0 的层次
最少边数本例访问次序
00
11、3
22、4、6
35、7
48

同一距离层内部的先后取决于邻居的检查次序,因此广度优先遍历序列并不唯一。

1.   算法实现

BFS 通常借助队列来实现,代码如下所示。队列具有“先入先出”的性质,这与 BFS 的“由近及远”的思想异曲同工。

  1. 将遍历起始顶点 startVet 加入队列,并开启循环。
  2. 在循环的每轮迭代中,弹出队首顶点并记录访问,然后将该顶点的所有邻接顶点加入到队列尾部。
  3. 循环步骤 2. ,直到所有顶点被访问完毕后结束。

为了防止重复遍历顶点,我们需要借助一个哈希集合 visited 来记录哪些节点已被访问。

Tip

哈希集合可以看作一个只存储 key 而不存储 value 的哈希表,它可以在 \(O(1)\) 时间复杂度下进行 key 的增删查改操作。根据 key 的唯一性,哈希集合通常用于数据去重等场景。

graph_bfs.py
def graph_bfs(graph: GraphAdjList, start_vet: Vertex) -> list[Vertex]:
    """广度优先遍历"""
    # 使用邻接表来表示图,以便获取指定顶点的所有邻接顶点
    # 顶点遍历序列
    res = []
    # 哈希集合,用于记录已被访问过的顶点
    visited = set[Vertex]([start_vet])
    # 队列用于实现 BFS
    que = deque[Vertex]([start_vet])
    # 以顶点 vet 为起点,循环直至访问完所有顶点
    while len(que) > 0:
        vet = que.popleft()  # 队首顶点出队
        res.append(vet)  # 记录访问顶点
        # 遍历该顶点的所有邻接顶点
        for adj_vet in graph.adj_list[vet]:
            if adj_vet in visited:
                continue  # 跳过已被访问的顶点
            que.append(adj_vet)  # 只入队未访问的顶点
            visited.add(adj_vet)  # 标记该顶点已被访问
    # 返回顶点遍历序列
    return res
graph_bfs.cpp
/* 广度优先遍历 */
// 使用邻接表来表示图,以便获取指定顶点的所有邻接顶点
vector<Vertex *> graphBFS(GraphAdjList &graph, Vertex *startVet) {
    // 顶点遍历序列
    vector<Vertex *> res;
    // 哈希集合,用于记录已被访问过的顶点
    unordered_set<Vertex *> visited = {startVet};
    // 队列用于实现 BFS
    queue<Vertex *> que;
    que.push(startVet);
    // 以顶点 vet 为起点,循环直至访问完所有顶点
    while (!que.empty()) {
        Vertex *vet = que.front();
        que.pop();          // 队首顶点出队
        res.push_back(vet); // 记录访问顶点
        // 遍历该顶点的所有邻接顶点
        for (auto adjVet : graph.adjList[vet]) {
            if (visited.count(adjVet))
                continue;            // 跳过已被访问的顶点
            que.push(adjVet);        // 只入队未访问的顶点
            visited.emplace(adjVet); // 标记该顶点已被访问
        }
    }
    // 返回顶点遍历序列
    return res;
}
graph_bfs.java
/* 广度优先遍历 */
// 使用邻接表来表示图,以便获取指定顶点的所有邻接顶点
List<Vertex> graphBFS(GraphAdjList graph, Vertex startVet) {
    // 顶点遍历序列
    List<Vertex> res = new ArrayList<>();
    // 哈希集合,用于记录已被访问过的顶点
    Set<Vertex> visited = new HashSet<>();
    visited.add(startVet);
    // 队列用于实现 BFS
    Queue<Vertex> que = new LinkedList<>();
    que.offer(startVet);
    // 以顶点 vet 为起点,循环直至访问完所有顶点
    while (!que.isEmpty()) {
        Vertex vet = que.poll(); // 队首顶点出队
        res.add(vet);            // 记录访问顶点
        // 遍历该顶点的所有邻接顶点
        for (Vertex adjVet : graph.adjList.get(vet)) {
            if (visited.contains(adjVet))
                continue;        // 跳过已被访问的顶点
            que.offer(adjVet);   // 只入队未访问的顶点
            visited.add(adjVet); // 标记该顶点已被访问
        }
    }
    // 返回顶点遍历序列
    return res;
}
graph_bfs.cs
/* 广度优先遍历 */
// 使用邻接表来表示图,以便获取指定顶点的所有邻接顶点
List<Vertex> GraphBFS(GraphAdjList graph, Vertex startVet) {
    // 顶点遍历序列
    List<Vertex> res = [];
    // 哈希集合,用于记录已被访问过的顶点
    HashSet<Vertex> visited = [startVet];
    // 队列用于实现 BFS
    Queue<Vertex> que = new();
    que.Enqueue(startVet);
    // 以顶点 vet 为起点,循环直至访问完所有顶点
    while (que.Count > 0) {
        Vertex vet = que.Dequeue(); // 队首顶点出队
        res.Add(vet);               // 记录访问顶点
        foreach (Vertex adjVet in graph.adjList[vet]) {
            if (visited.Contains(adjVet)) {
                continue;          // 跳过已被访问的顶点
            }
            que.Enqueue(adjVet);   // 只入队未访问的顶点
            visited.Add(adjVet);   // 标记该顶点已被访问
        }
    }

    // 返回顶点遍历序列
    return res;
}
graph_bfs.go
/* 广度优先遍历 */
// 使用邻接表来表示图,以便获取指定顶点的所有邻接顶点
func graphBFS(g *graphAdjList, startVet Vertex) []Vertex {
    // 顶点遍历序列
    res := make([]Vertex, 0)
    // 哈希集合,用于记录已被访问过的顶点
    visited := make(map[Vertex]struct{})
    visited[startVet] = struct{}{}
    // 队列用于实现 BFS, 使用切片模拟队列
    queue := make([]Vertex, 0)
    queue = append(queue, startVet)
    // 以顶点 vet 为起点,循环直至访问完所有顶点
    for len(queue) > 0 {
        // 队首顶点出队
        vet := queue[0]
        queue = queue[1:]
        // 记录访问顶点
        res = append(res, vet)
        // 遍历该顶点的所有邻接顶点
        for _, adjVet := range g.adjList[vet] {
            _, isExist := visited[adjVet]
            // 只入队未访问的顶点
            if !isExist {
                queue = append(queue, adjVet)
                visited[adjVet] = struct{}{}
            }
        }
    }
    // 返回顶点遍历序列
    return res
}
graph_bfs.swift
/* 广度优先遍历 */
// 使用邻接表来表示图,以便获取指定顶点的所有邻接顶点
func graphBFS(graph: GraphAdjList, startVet: Vertex) -> [Vertex] {
    // 顶点遍历序列
    var res: [Vertex] = []
    // 哈希集合,用于记录已被访问过的顶点
    var visited: Set<Vertex> = [startVet]
    // 队列用于实现 BFS
    var que: [Vertex] = [startVet]
    // 以顶点 vet 为起点,循环直至访问完所有顶点
    while !que.isEmpty {
        let vet = que.removeFirst() // 队首顶点出队
        res.append(vet) // 记录访问顶点
        // 遍历该顶点的所有邻接顶点
        for adjVet in graph.adjList[vet] ?? [] {
            if visited.contains(adjVet) {
                continue // 跳过已被访问的顶点
            }
            que.append(adjVet) // 只入队未访问的顶点
            visited.insert(adjVet) // 标记该顶点已被访问
        }
    }
    // 返回顶点遍历序列
    return res
}
graph_bfs.js
/* 广度优先遍历 */
// 使用邻接表来表示图,以便获取指定顶点的所有邻接顶点
function graphBFS(graph, startVet) {
    // 顶点遍历序列
    const res = [];
    // 哈希集合,用于记录已被访问过的顶点
    const visited = new Set();
    visited.add(startVet);
    // 队列用于实现 BFS
    const que = [startVet];
    // 以顶点 vet 为起点,循环直至访问完所有顶点
    while (que.length) {
        const vet = que.shift(); // 队首顶点出队
        res.push(vet); // 记录访问顶点
        // 遍历该顶点的所有邻接顶点
        for (const adjVet of graph.adjList.get(vet) ?? []) {
            if (visited.has(adjVet)) {
                continue; // 跳过已被访问的顶点
            }
            que.push(adjVet); // 只入队未访问的顶点
            visited.add(adjVet); // 标记该顶点已被访问
        }
    }
    // 返回顶点遍历序列
    return res;
}
graph_bfs.ts
/* 广度优先遍历 */
// 使用邻接表来表示图,以便获取指定顶点的所有邻接顶点
function graphBFS(graph: GraphAdjList, startVet: Vertex): Vertex[] {
    // 顶点遍历序列
    const res: Vertex[] = [];
    // 哈希集合,用于记录已被访问过的顶点
    const visited: Set<Vertex> = new Set();
    visited.add(startVet);
    // 队列用于实现 BFS
    const que = [startVet];
    // 以顶点 vet 为起点,循环直至访问完所有顶点
    while (que.length) {
        const vet = que.shift(); // 队首顶点出队
        res.push(vet); // 记录访问顶点
        // 遍历该顶点的所有邻接顶点
        for (const adjVet of graph.adjList.get(vet) ?? []) {
            if (visited.has(adjVet)) {
                continue; // 跳过已被访问的顶点
            }
            que.push(adjVet); // 只入队未访问
            visited.add(adjVet); // 标记该顶点已被访问
        }
    }
    // 返回顶点遍历序列
    return res;
}
graph_bfs.dart
/* 广度优先遍历 */
List<Vertex> graphBFS(GraphAdjList graph, Vertex startVet) {
  // 使用邻接表来表示图,以便获取指定顶点的所有邻接顶点
  // 顶点遍历序列
  List<Vertex> res = [];
  // 哈希集合,用于记录已被访问过的顶点
  Set<Vertex> visited = {};
  visited.add(startVet);
  // 队列用于实现 BFS
  Queue<Vertex> que = Queue();
  que.add(startVet);
  // 以顶点 vet 为起点,循环直至访问完所有顶点
  while (que.isNotEmpty) {
    Vertex vet = que.removeFirst(); // 队首顶点出队
    res.add(vet); // 记录访问顶点
    // 遍历该顶点的所有邻接顶点
    for (Vertex adjVet in graph.adjList[vet]!) {
      if (visited.contains(adjVet)) {
        continue; // 跳过已被访问的顶点
      }
      que.add(adjVet); // 只入队未访问的顶点
      visited.add(adjVet); // 标记该顶点已被访问
    }
  }
  // 返回顶点遍历序列
  return res;
}
graph_bfs.rs
/* 广度优先遍历 */
// 使用邻接表来表示图,以便获取指定顶点的所有邻接顶点
fn graph_bfs(graph: GraphAdjList, start_vet: Vertex) -> Vec<Vertex> {
    // 顶点遍历序列
    let mut res = vec![];
    // 哈希集合,用于记录已被访问过的顶点
    let mut visited = HashSet::new();
    visited.insert(start_vet);
    // 队列用于实现 BFS
    let mut que = VecDeque::new();
    que.push_back(start_vet);
    // 以顶点 vet 为起点,循环直至访问完所有顶点
    while let Some(vet) = que.pop_front() {
        res.push(vet); // 记录访问顶点

        // 遍历该顶点的所有邻接顶点
        if let Some(adj_vets) = graph.adj_list.get(&vet) {
            for &adj_vet in adj_vets {
                if visited.contains(&adj_vet) {
                    continue; // 跳过已被访问的顶点
                }
                que.push_back(adj_vet); // 只入队未访问的顶点
                visited.insert(adj_vet); // 标记该顶点已被访问
            }
        }
    }
    // 返回顶点遍历序列
    res
}
graph_bfs.c
/* 节点队列结构体 */
typedef struct {
    Vertex *vertices[MAX_SIZE];
    int front, rear, size;
} Queue;

/* 构造函数 */
Queue *newQueue() {
    Queue *q = (Queue *)malloc(sizeof(Queue));
    q->front = q->rear = q->size = 0;
    return q;
}

/* 判断队列是否为空 */
int isEmpty(Queue *q) {
    return q->size == 0;
}

/* 入队操作 */
void enqueue(Queue *q, Vertex *vet) {
    q->vertices[q->rear] = vet;
    q->rear = (q->rear + 1) % MAX_SIZE;
    q->size++;
}

/* 出队操作 */
Vertex *dequeue(Queue *q) {
    Vertex *vet = q->vertices[q->front];
    q->front = (q->front + 1) % MAX_SIZE;
    q->size--;
    return vet;
}

/* 检查顶点是否已被访问 */
int isVisited(Vertex **visited, int size, Vertex *vet) {
    // 遍历查找节点,使用 O(n) 时间
    for (int i = 0; i < size; i++) {
        if (visited[i] == vet)
            return 1;
    }
    return 0;
}

/* 广度优先遍历 */
// 使用邻接表来表示图,以便获取指定顶点的所有邻接顶点
void graphBFS(GraphAdjList *graph, Vertex *startVet, Vertex **res, int *resSize, Vertex **visited, int *visitedSize) {
    // 队列用于实现 BFS
    Queue *queue = newQueue();
    enqueue(queue, startVet);
    visited[(*visitedSize)++] = startVet;
    // 以顶点 vet 为起点,循环直至访问完所有顶点
    while (!isEmpty(queue)) {
        Vertex *vet = dequeue(queue); // 队首顶点出队
        res[(*resSize)++] = vet;      // 记录访问顶点
        // 遍历该顶点的所有邻接顶点
        AdjListNode *node = findNode(graph, vet);
        while (node != NULL) {
            // 跳过已被访问的顶点
            if (!isVisited(visited, *visitedSize, node->vertex)) {
                enqueue(queue, node->vertex);             // 只入队未访问的顶点
                visited[(*visitedSize)++] = node->vertex; // 标记该顶点已被访问
            }
            node = node->next;
        }
    }
    // 释放内存
    free(queue);
}
graph_bfs.kt
/* 广度优先遍历 */
// 使用邻接表来表示图,以便获取指定顶点的所有邻接顶点
fun graphBFS(graph: GraphAdjList, startVet: Vertex): MutableList<Vertex?> {
    // 顶点遍历序列
    val res = mutableListOf<Vertex?>()
    // 哈希集合,用于记录已被访问过的顶点
    val visited = HashSet<Vertex>()
    visited.add(startVet)
    // 队列用于实现 BFS
    val que = LinkedList<Vertex>()
    que.offer(startVet)
    // 以顶点 vet 为起点,循环直至访问完所有顶点
    while (!que.isEmpty()) {
        val vet = que.poll() // 队首顶点出队
        res.add(vet)         // 记录访问顶点
        // 遍历该顶点的所有邻接顶点
        for (adjVet in graph.adjList[vet]!!) {
            if (visited.contains(adjVet))
                continue        // 跳过已被访问的顶点
            que.offer(adjVet)   // 只入队未访问的顶点
            visited.add(adjVet) // 标记该顶点已被访问
        }
    }
    // 返回顶点遍历序列
    return res
}
graph_bfs.rb
### 广度优先遍历 ###
def graph_bfs(graph, start_vet)
  # 使用邻接表来表示图,以便获取指定顶点的所有邻接顶点
  # 顶点遍历序列
  res = []
  # 哈希集合,用于记录已被访问过的顶点
  visited = Set.new([start_vet])
  # 队列用于实现 BFS
  que = [start_vet]
  # 以顶点 vet 为起点,循环直至访问完所有顶点
  while que.length > 0
    vet = que.shift # 队首顶点出队
    res << vet # 记录访问顶点
    # 遍历该顶点的所有邻接顶点
    for adj_vet in graph.adj_list[vet]
      next if visited.include?(adj_vet) # 跳过已被访问的顶点
      que << adj_vet # 只入队未访问的顶点
      visited.add(adj_vet) # 标记该顶点已被访问
    end
  end
  # 返回顶点遍历序列
  res
end
可视化运行

代码相对抽象,建议对照图 9-10 来加深理解。

图 9-10   图的广度优先遍历步骤

图解 9-10:图的广度优先遍历:操作过程

从左上角起点 0 出发,按到起点的最少边数由近及远逐层访问顶点。

待遍历的无向图有 9 个顶点,编号为 0 至 8,按三行三列网格排列:三行依次为 0、1、2;3、4、5;6、7、8。图中只在水平或竖直相邻的顶点之间连接无向边,共 12 条边,没有对角边;各顶点的邻居列在邻接表中。

原图的邻接关系,共十二条无向边
顶点相邻顶点
01、3
10、2、4
21、5
30、4、6
41、3、5、7
52、4、8
63、7
74、6、8
85、7
  1. 初始化队列和集合

    过程图用 res 记录已出队顶点,用队列 que 存放待处理顶点(从队首到队尾书写),用集合 visited 记录已发现顶点。顶点入队时立即记入 visited,无须等到出队,因此还在排队的顶点也不会重复入队。队列左侧空白格是出队后的旧槽位,不是空元素;visited 的横向排列及下文花括号都不表示集合内部有序。初始把 0 入队并记为已发现:res=[],que=[0],visited={0},尚无顶点出队。

  2. 处理顶点 0

    队首顶点 0 出队并追加到 res。检查 0 的邻居 1、3,两者均未发现,依次加入队列 que 队尾并记入 visited。当前结果 res=[0];待处理队列 que=[1, 3];已发现集合 visited={0, 1, 3}。

  3. 处理顶点 1

    队首顶点 1 出队并追加到 res。在 1 的邻居 0、2、4 中,0 已在 visited 中故跳过;未发现的新邻居 2、4 依次入队并记入 visited。当前结果 res=[0, 1];待处理队列 que=[3, 2, 4];已发现集合 visited={0, 1, 3, 2, 4}。

  4. 处理顶点 3

    队首顶点 3 出队并追加到 res。在 3 的邻居 0、4、6 中,0 和 4 均已在 visited 中而跳过,仅将新邻居 6 入队并记入 visited。其中顶点 4 在上一步已由顶点 1 发现并入队,虽仍在队列中等待出队,也不会重复加入。当前结果 res=[0, 1, 3];待处理队列 que=[2, 4, 6];已发现集合 visited={0, 1, 3, 2, 4, 6}。

  5. 处理顶点 2

    队首顶点 2 出队并追加到 res。在 2 的邻居 1、5 中,1 已在 visited 中故跳过;将新邻居 5 入队并记入 visited。当前结果 res=[0, 1, 3, 2];待处理队列 que=[4, 6, 5];已发现集合 visited={0, 1, 3, 2, 4, 6, 5}。

  6. 处理顶点 4

    队首顶点 4 出队并追加到 res。在 4 的邻居 1、3、5、7 中,1、3、5 均已在 visited 中故跳过;将新邻居 7 入队并记入 visited。当前结果 res=[0, 1, 3, 2, 4];待处理队列 que=[6, 5, 7];已发现集合 visited={0, 1, 3, 2, 4, 6, 5, 7}。

  7. 处理顶点 6

    队首顶点 6 出队并追加到 res。它的邻居 3、7 均已在 visited 中(其中 7 已在上一步由 4 发现并入队),因此本轮没有新邻居入队。当前结果 res=[0, 1, 3, 2, 4, 6];待处理队列 que=[5, 7];已发现集合 visited={0, 1, 3, 2, 4, 6, 5, 7}。

  8. 处理顶点 5

    队首顶点 5 出队并追加到 res。在 5 的邻居 2、4、8 中,2、4 已在 visited 中故跳过;将最后一个新邻居 8 入队并记入 visited。至此九个顶点均已发现,但队列中的 7、8 仍待出队处理。当前结果 res=[0, 1, 3, 2, 4, 6, 5];待处理队列 que=[7, 8];已发现集合 visited={0, 1, 3, 2, 4, 6, 5, 7, 8}。

  9. 处理顶点 7

    队首顶点 7 出队并追加到 res。它的邻居 4、6、8 均已在 visited 中,没有新邻居入队,队列中仅剩 8。当前结果 res=[0, 1, 3, 2, 4, 6, 5, 7];待处理队列 que=[8];已发现集合 visited={0, 1, 3, 2, 4, 6, 5, 7, 8}。

  10. 处理顶点 8

    队首顶点 8 出队并追加到 res。它的邻居 5、7 均已在 visited 中,没有新邻居入队,队列 que 至此清空。当前结果 res=[0, 1, 3, 2, 4, 6, 5, 7, 8];待处理队列 que=[];已发现集合 visited={0, 1, 3, 2, 4, 6, 5, 7, 8}。

  11. 返回遍历结果

    队列 que=[],循环结束并返回 res=[0, 1, 3, 2, 4, 6, 5, 7, 8];visited 包含 0 至 8 全部顶点。

同一距离层内部的先后取决于邻居的检查次序,因此广度优先遍历序列并不唯一。

广度优先遍历的序列是否唯一?

不唯一。广度优先遍历只要求按“由近及远”的顺序遍历,而多个相同距离的顶点的遍历顺序允许被任意打乱。以图 9-10 为例,顶点 \(1\)、\(3\) 的访问顺序可以交换,顶点 \(2\)、\(4\)、\(6\) 的访问顺序也可以任意交换。

2.   复杂度分析

时间复杂度:所有顶点都会入队并出队一次,使用 \(O(|V|)\) 时间;在遍历邻接顶点的过程中,由于是无向图,因此所有边都会被访问 \(2\) 次,使用 \(O(2|E|)\) 时间;总体使用 \(O(|V| + |E|)\) 时间。

空间复杂度:列表 res ,哈希集合 visited ,队列 que 中的顶点数量最多为 \(|V|\) ,使用 \(O(|V|)\) 空间。

9.3.2   深度优先遍历

深度优先遍历是一种优先走到底、无路可走再回头的遍历方式。如图 9-11 所示,从左上角顶点出发,访问当前顶点的某个邻接顶点,直到走到尽头时返回,再继续走到尽头并返回,以此类推,直至所有顶点遍历完成。

图 9-11   图的深度优先遍历

图解 9-11:图的深度优先遍历:概览

从起点出发沿未访问邻居递归深入,无路可走时回溯到上一层顶点,继续探索剩余分支。

无向连通图包含顶点 0 至 6,共 6 条无向边:0—1、0—3、1—2、2—5、4—5、5—6。遍历从起点 0 出发;本例在顶点 0 处按先 1 后 3 的次序检查邻居,在顶点 5 处按先 4 后 6 的次序检查邻居。

灰色实线是无向图原边;蓝色直虚线表示递归进入未访问邻居,橙色曲虚线表示调用结束后返回,均不是新增的图边。概览中的括号编号 1 至 14 表示 7 次进入与 7 次返回(包括起始调用进入和最外层调用返回),不是顶点编号。

过程图把这 14 个事件展示为 11 步:第 1 至 8 步对应事件 1 至 8,第 9 步合并事件 9 至 11,第 10 步对应事件 12,第 11 步合并事件 13 至 14。

原图邻接关系
顶点邻居
01、3
10、2
21、5
30
45
52、4、6
65

进入起点 0 后依次深入 1、2、5、4(事件 1 至 5);4 返回 5(事件 6),再从 5 深入 6 并返回(事件 7、8)。随后沿 5→2→1→0 连续返回(事件 9 至 11),转入 0 的剩余分支 3(事件 12),最后从 3 返回 0 并结束起始调用(事件 13、14)。完整首次访问序列为 [0, 1, 2, 5, 4, 6, 3];下表按图中编号列出事件,返回事件不新增访问。

递归进入与返回事件
图中事件编号动作是否新增访问
1进入起点0新增0
20递归进入1新增1
31递归进入2新增2
42递归进入5新增5
55递归进入4新增4
64返回5不新增
75递归进入6新增6
86返回5不新增
95返回2不新增
102返回1不新增
111返回0不新增
120递归进入3新增3
133返回0不新增
14起始调用返回不新增

res 只记录首次访问,回溯不追加顶点。改变邻居检查次序,所得深度优先序列也会改变;全部顶点已访问之后,还须结束剩余递归调用。

1.   算法实现

这种“走到尽头再返回”的算法范式通常基于递归来实现。与广度优先遍历类似,在深度优先遍历中,我们也需要借助一个哈希集合 visited 来记录已被访问的顶点,以避免重复访问顶点。

graph_dfs.py
def dfs(graph: GraphAdjList, visited: set[Vertex], res: list[Vertex], vet: Vertex):
    """深度优先遍历辅助函数"""
    res.append(vet)  # 记录访问顶点
    visited.add(vet)  # 标记该顶点已被访问
    # 遍历该顶点的所有邻接顶点
    for adjVet in graph.adj_list[vet]:
        if adjVet in visited:
            continue  # 跳过已被访问的顶点
        # 递归访问邻接顶点
        dfs(graph, visited, res, adjVet)

def graph_dfs(graph: GraphAdjList, start_vet: Vertex) -> list[Vertex]:
    """深度优先遍历"""
    # 使用邻接表来表示图,以便获取指定顶点的所有邻接顶点
    # 顶点遍历序列
    res = []
    # 哈希集合,用于记录已被访问过的顶点
    visited = set[Vertex]()
    dfs(graph, visited, res, start_vet)
    return res
graph_dfs.cpp
/* 深度优先遍历辅助函数 */
void dfs(GraphAdjList &graph, unordered_set<Vertex *> &visited, vector<Vertex *> &res, Vertex *vet) {
    res.push_back(vet);   // 记录访问顶点
    visited.emplace(vet); // 标记该顶点已被访问
    // 遍历该顶点的所有邻接顶点
    for (Vertex *adjVet : graph.adjList[vet]) {
        if (visited.count(adjVet))
            continue; // 跳过已被访问的顶点
        // 递归访问邻接顶点
        dfs(graph, visited, res, adjVet);
    }
}

/* 深度优先遍历 */
// 使用邻接表来表示图,以便获取指定顶点的所有邻接顶点
vector<Vertex *> graphDFS(GraphAdjList &graph, Vertex *startVet) {
    // 顶点遍历序列
    vector<Vertex *> res;
    // 哈希集合,用于记录已被访问过的顶点
    unordered_set<Vertex *> visited;
    dfs(graph, visited, res, startVet);
    return res;
}
graph_dfs.java
/* 深度优先遍历辅助函数 */
void dfs(GraphAdjList graph, Set<Vertex> visited, List<Vertex> res, Vertex vet) {
    res.add(vet);     // 记录访问顶点
    visited.add(vet); // 标记该顶点已被访问
    // 遍历该顶点的所有邻接顶点
    for (Vertex adjVet : graph.adjList.get(vet)) {
        if (visited.contains(adjVet))
            continue; // 跳过已被访问的顶点
        // 递归访问邻接顶点
        dfs(graph, visited, res, adjVet);
    }
}

/* 深度优先遍历 */
// 使用邻接表来表示图,以便获取指定顶点的所有邻接顶点
List<Vertex> graphDFS(GraphAdjList graph, Vertex startVet) {
    // 顶点遍历序列
    List<Vertex> res = new ArrayList<>();
    // 哈希集合,用于记录已被访问过的顶点
    Set<Vertex> visited = new HashSet<>();
    dfs(graph, visited, res, startVet);
    return res;
}
graph_dfs.cs
/* 深度优先遍历辅助函数 */
void DFS(GraphAdjList graph, HashSet<Vertex> visited, List<Vertex> res, Vertex vet) {
    res.Add(vet);     // 记录访问顶点
    visited.Add(vet); // 标记该顶点已被访问
    // 遍历该顶点的所有邻接顶点
    foreach (Vertex adjVet in graph.adjList[vet]) {
        if (visited.Contains(adjVet)) {
            continue; // 跳过已被访问的顶点                             
        }
        // 递归访问邻接顶点
        DFS(graph, visited, res, adjVet);
    }
}

/* 深度优先遍历 */
// 使用邻接表来表示图,以便获取指定顶点的所有邻接顶点
List<Vertex> GraphDFS(GraphAdjList graph, Vertex startVet) {
    // 顶点遍历序列
    List<Vertex> res = [];
    // 哈希集合,用于记录已被访问过的顶点
    HashSet<Vertex> visited = [];
    DFS(graph, visited, res, startVet);
    return res;
}
graph_dfs.go
/* 深度优先遍历辅助函数 */
func dfs(g *graphAdjList, visited map[Vertex]struct{}, res *[]Vertex, vet Vertex) {
    // append 操作会返回新的的引用,必须让原引用重新赋值为新slice的引用
    *res = append(*res, vet)
    visited[vet] = struct{}{}
    // 遍历该顶点的所有邻接顶点
    for _, adjVet := range g.adjList[vet] {
        _, isExist := visited[adjVet]
        // 递归访问邻接顶点
        if !isExist {
            dfs(g, visited, res, adjVet)
        }
    }
}

/* 深度优先遍历 */
// 使用邻接表来表示图,以便获取指定顶点的所有邻接顶点
func graphDFS(g *graphAdjList, startVet Vertex) []Vertex {
    // 顶点遍历序列
    res := make([]Vertex, 0)
    // 哈希集合,用于记录已被访问过的顶点
    visited := make(map[Vertex]struct{})
    dfs(g, visited, &res, startVet)
    // 返回顶点遍历序列
    return res
}
graph_dfs.swift
/* 深度优先遍历辅助函数 */
func dfs(graph: GraphAdjList, visited: inout Set<Vertex>, res: inout [Vertex], vet: Vertex) {
    res.append(vet) // 记录访问顶点
    visited.insert(vet) // 标记该顶点已被访问
    // 遍历该顶点的所有邻接顶点
    for adjVet in graph.adjList[vet] ?? [] {
        if visited.contains(adjVet) {
            continue // 跳过已被访问的顶点
        }
        // 递归访问邻接顶点
        dfs(graph: graph, visited: &visited, res: &res, vet: adjVet)
    }
}

/* 深度优先遍历 */
// 使用邻接表来表示图,以便获取指定顶点的所有邻接顶点
func graphDFS(graph: GraphAdjList, startVet: Vertex) -> [Vertex] {
    // 顶点遍历序列
    var res: [Vertex] = []
    // 哈希集合,用于记录已被访问过的顶点
    var visited: Set<Vertex> = []
    dfs(graph: graph, visited: &visited, res: &res, vet: startVet)
    return res
}
graph_dfs.js
/* 深度优先遍历 */
// 使用邻接表来表示图,以便获取指定顶点的所有邻接顶点
function dfs(graph, visited, res, vet) {
    res.push(vet); // 记录访问顶点
    visited.add(vet); // 标记该顶点已被访问
    // 遍历该顶点的所有邻接顶点
    for (const adjVet of graph.adjList.get(vet)) {
        if (visited.has(adjVet)) {
            continue; // 跳过已被访问的顶点
        }
        // 递归访问邻接顶点
        dfs(graph, visited, res, adjVet);
    }
}

/* 深度优先遍历 */
// 使用邻接表来表示图,以便获取指定顶点的所有邻接顶点
function graphDFS(graph, startVet) {
    // 顶点遍历序列
    const res = [];
    // 哈希集合,用于记录已被访问过的顶点
    const visited = new Set();
    dfs(graph, visited, res, startVet);
    return res;
}
graph_dfs.ts
/* 深度优先遍历辅助函数 */
function dfs(
    graph: GraphAdjList,
    visited: Set<Vertex>,
    res: Vertex[],
    vet: Vertex
): void {
    res.push(vet); // 记录访问顶点
    visited.add(vet); // 标记该顶点已被访问
    // 遍历该顶点的所有邻接顶点
    for (const adjVet of graph.adjList.get(vet)) {
        if (visited.has(adjVet)) {
            continue; // 跳过已被访问的顶点
        }
        // 递归访问邻接顶点
        dfs(graph, visited, res, adjVet);
    }
}

/* 深度优先遍历 */
// 使用邻接表来表示图,以便获取指定顶点的所有邻接顶点
function graphDFS(graph: GraphAdjList, startVet: Vertex): Vertex[] {
    // 顶点遍历序列
    const res: Vertex[] = [];
    // 哈希集合,用于记录已被访问过的顶点
    const visited: Set<Vertex> = new Set();
    dfs(graph, visited, res, startVet);
    return res;
}
graph_dfs.dart
/* 深度优先遍历辅助函数 */
void dfs(
  GraphAdjList graph,
  Set<Vertex> visited,
  List<Vertex> res,
  Vertex vet,
) {
  res.add(vet); // 记录访问顶点
  visited.add(vet); // 标记该顶点已被访问
  // 遍历该顶点的所有邻接顶点
  for (Vertex adjVet in graph.adjList[vet]!) {
    if (visited.contains(adjVet)) {
      continue; // 跳过已被访问的顶点
    }
    // 递归访问邻接顶点
    dfs(graph, visited, res, adjVet);
  }
}

/* 深度优先遍历 */
List<Vertex> graphDFS(GraphAdjList graph, Vertex startVet) {
  // 顶点遍历序列
  List<Vertex> res = [];
  // 哈希集合,用于记录已被访问过的顶点
  Set<Vertex> visited = {};
  dfs(graph, visited, res, startVet);
  return res;
}
graph_dfs.rs
/* 深度优先遍历辅助函数 */
fn dfs(graph: &GraphAdjList, visited: &mut HashSet<Vertex>, res: &mut Vec<Vertex>, vet: Vertex) {
    res.push(vet); // 记录访问顶点
    visited.insert(vet); // 标记该顶点已被访问
                         // 遍历该顶点的所有邻接顶点
    if let Some(adj_vets) = graph.adj_list.get(&vet) {
        for &adj_vet in adj_vets {
            if visited.contains(&adj_vet) {
                continue; // 跳过已被访问的顶点
            }
            // 递归访问邻接顶点
            dfs(graph, visited, res, adj_vet);
        }
    }
}

/* 深度优先遍历 */
// 使用邻接表来表示图,以便获取指定顶点的所有邻接顶点
fn graph_dfs(graph: GraphAdjList, start_vet: Vertex) -> Vec<Vertex> {
    // 顶点遍历序列
    let mut res = vec![];
    // 哈希集合,用于记录已被访问过的顶点
    let mut visited = HashSet::new();
    dfs(&graph, &mut visited, &mut res, start_vet);

    res
}
graph_dfs.c
/* 检查顶点是否已被访问 */
int isVisited(Vertex **res, int size, Vertex *vet) {
    // 遍历查找节点,使用 O(n) 时间
    for (int i = 0; i < size; i++) {
        if (res[i] == vet) {
            return 1;
        }
    }
    return 0;
}

/* 深度优先遍历辅助函数 */
void dfs(GraphAdjList *graph, Vertex **res, int *resSize, Vertex *vet) {
    // 记录访问顶点
    res[(*resSize)++] = vet;
    // 遍历该顶点的所有邻接顶点
    AdjListNode *node = findNode(graph, vet);
    while (node != NULL) {
        // 跳过已被访问的顶点
        if (!isVisited(res, *resSize, node->vertex)) {
            // 递归访问邻接顶点
            dfs(graph, res, resSize, node->vertex);
        }
        node = node->next;
    }
}

/* 深度优先遍历 */
// 使用邻接表来表示图,以便获取指定顶点的所有邻接顶点
void graphDFS(GraphAdjList *graph, Vertex *startVet, Vertex **res, int *resSize) {
    dfs(graph, res, resSize, startVet);
}
graph_dfs.kt
/* 深度优先遍历辅助函数 */
fun dfs(
    graph: GraphAdjList,
    visited: MutableSet<Vertex?>,
    res: MutableList<Vertex?>,
    vet: Vertex?
) {
    res.add(vet)     // 记录访问顶点
    visited.add(vet) // 标记该顶点已被访问
    // 遍历该顶点的所有邻接顶点
    for (adjVet in graph.adjList[vet]!!) {
        if (visited.contains(adjVet))
            continue  // 跳过已被访问的顶点
        // 递归访问邻接顶点
        dfs(graph, visited, res, adjVet)
    }
}

/* 深度优先遍历 */
// 使用邻接表来表示图,以便获取指定顶点的所有邻接顶点
fun graphDFS(graph: GraphAdjList, startVet: Vertex?): MutableList<Vertex?> {
    // 顶点遍历序列
    val res = mutableListOf<Vertex?>()
    // 哈希集合,用于记录已被访问过的顶点
    val visited = HashSet<Vertex?>()
    dfs(graph, visited, res, startVet)
    return res
}
graph_dfs.rb
### 深度优先遍历辅助函数 ###
def dfs(graph, visited, res, vet)
  res << vet # 记录访问顶点
  visited.add(vet) # 标记该顶点已被访问
  # 遍历该顶点的所有邻接顶点
  for adj_vet in graph.adj_list[vet]
    next if visited.include?(adj_vet) # 跳过已被访问的顶点
    # 递归访问邻接顶点
    dfs(graph, visited, res, adj_vet)
  end
end

### 深度优先遍历 ###
def graph_dfs(graph, start_vet)
  # 使用邻接表来表示图,以便获取指定顶点的所有邻接顶点
  # 顶点遍历序列
  res = []
  # 哈希集合,用于记录已被访问过的顶点
  visited = Set.new
  dfs(graph, visited, res, start_vet)
  res
end
可视化运行

深度优先遍历的算法流程如图 9-12 所示。

  • 直虚线代表向下递推,表示开启了一个新的递归方法来访问新顶点。
  • 曲虚线代表向上回溯,表示此递归方法已经返回,回溯到了开启此方法的位置。

为了加深理解,建议将图 9-12 与代码结合起来,在脑中模拟(或者用笔画下来)整个 DFS 过程,包括每个递归方法何时开启、何时返回。

图 9-12   图的深度优先遍历步骤

图解 9-12:图的深度优先遍历:操作过程

从起点出发沿未访问邻居递归深入,无路可走时回溯到上一层顶点,继续探索剩余分支。

无向连通图包含顶点 0 至 6,共 6 条无向边:0—1、0—3、1—2、2—5、4—5、5—6。遍历从起点 0 出发;本例在顶点 0 处按先 1 后 3 的次序检查邻居,在顶点 5 处按先 4 后 6 的次序检查邻居。

灰色实线是无向图原边;蓝色直虚线表示递归进入未访问邻居,橙色曲虚线表示调用结束后返回,均不是新增的图边。概览中的括号编号 1 至 14 表示 7 次进入与 7 次返回(包括起始调用进入和最外层调用返回),不是顶点编号。

过程图把这 14 个事件展示为 11 步:第 1 至 8 步对应事件 1 至 8,第 9 步合并事件 9 至 11,第 10 步对应事件 12,第 11 步合并事件 13 至 14。

原图邻接关系
顶点邻居
01、3
10、2
21、5
30
45
52、4、6
65
  1. 访问起点 0

    过程图用 res 按首次访问顺序记录顶点,visited 用于去重;花括号只列集合成员,不表示顺序。起始调用进入顶点 0(事件 1),先记入 res、visited,再按先 1 后 3 检查邻居。当前递归调用路径为 0;res = [0],visited = {0};0 的邻居 1、3 均未访问。

  2. 从 0 深入 1

    顶点 0 有未访问邻居 1 和 3,本例先递归进入 1(事件 2),将首次访问的 1 记入 res 和 visited;另一邻居 3 留待 1 的分支返回后再探索。当前递归调用路径为 0→1;res = [0, 1],visited = {0, 1}。

  3. 从 1 深入 2

    顶点 1 的邻居 0 已在 visited 中,跳过 0,递归进入未访问的邻居 2(事件 3),将 2 记入 res 和 visited。当前递归调用路径为 0→1→2;res = [0, 1, 2],visited = {0, 1, 2}。

  4. 从 2 深入 5

    顶点 2 的邻居 1 已访问,继续递归进入未访问的邻居 5(事件 4),将 5 记入 res 和 visited。当前递归调用路径为 0→1→2→5;res = [0, 1, 2, 5],visited = {0, 1, 2, 5};5 还有未访问邻居 4、6。

  5. 从 5 深入 4

    顶点 5 的邻居 2 已访问;在剩余未访问邻居 4、6 中,本例先递归进入 4(事件 5),将 4 记入 res 和 visited。当前递归调用路径为 0→1→2→5→4;res = [0, 1, 2, 5, 4],visited = {0, 1, 2, 4, 5};顶点 3、6 尚未访问。

  6. 从 4 返回 5

    顶点 4 的唯一邻居 5 已访问,结束对 4 的调用并返回 5(事件 6)。返回到已访问的 5 不会再次将它写入 res。当前递归调用路径为 0→1→2→5;res 仍为 [0, 1, 2, 5, 4],visited 仍为 {0, 1, 2, 4, 5};5 的邻居 6 与 0 的邻居 3 尚未访问。

  7. 从 5 深入 6

    回到顶点 5 后,继续检查其剩余未访问邻居 6,递归进入 6(事件 7)并将 6 记入 res 和 visited。当前递归调用路径为 0→1→2→5→6;res = [0, 1, 2, 5, 4, 6],visited = {0, 1, 2, 4, 5, 6};全图仅剩顶点 3 尚未访问。

  8. 从 6 返回 5

    顶点 6 的唯一邻居 5 已访问,结束对 6 的调用并返回 5(事件 8),没有新访问。当前递归调用路径为 0→1→2→5;res = [0, 1, 2, 5, 4, 6],visited = {0, 1, 2, 4, 5, 6};5 的全部邻居 2、4、6 均已处理完毕。

  9. 连续返回起点 0

    5、2、1 的邻居均已检查完毕,沿 5→2→1→0 连续回溯:事件 9 是 5 返回 2,事件 10 是 2 返回 1,事件 11 是 1 返回 0。当前递归调用路径为 0;res = [0, 1, 2, 5, 4, 6],visited = {0, 1, 2, 4, 5, 6};起点 0 尚有未访问的邻居分支 3 待探索。

  10. 从 0 深入 3

    0 的邻居 1 分支已全部返回,接着进入未访问邻居 3(事件 12),将 3 记入 res 和 visited。当前递归调用路径为 0→3;res = [0, 1, 2, 5, 4, 6, 3],visited = {0, 1, 2, 3, 4, 5, 6};全部 7 个顶点均已访问,尚待执行最后的调用返回。

  11. 结束全部递归调用

    顶点 3 唯一的邻居 0 已访问,先从 3 返回 0(事件 13);此时起点 0 的所有邻居也已处理完毕,最外层起始调用随之返回(事件 14),整场深度优先遍历正式结束。调用栈清空;最终 res = [0, 1, 2, 5, 4, 6, 3],visited = {0, 1, 2, 3, 4, 5, 6},图中起点 0 带有橙色返回标记。

res 只记录首次访问,回溯不追加顶点。改变邻居检查次序,所得深度优先序列也会改变;全部顶点已访问之后,还须结束剩余递归调用。

深度优先遍历的序列是否唯一?

与广度优先遍历类似,深度优先遍历序列的顺序也不是唯一的。给定某顶点,先往哪个方向探索都可以,即邻接顶点的顺序可以任意打乱,都是深度优先遍历。

以树的遍历为例,“根 \(\rightarrow\) 左 \(\rightarrow\) 右”“左 \(\rightarrow\) 根 \(\rightarrow\) 右”“左 \(\rightarrow\) 右 \(\rightarrow\) 根”分别对应前序、中序、后序遍历,它们展示了三种遍历优先级,然而这三者都属于深度优先遍历。

2.   复杂度分析

时间复杂度:所有顶点都会被访问 \(1\) 次,使用 \(O(|V|)\) 时间;所有边都会被访问 \(2\) 次,使用 \(O(2|E|)\) 时间;总体使用 \(O(|V| + |E|)\) 时间。

空间复杂度:列表 res ,哈希集合 visited 顶点数量最多为 \(|V|\) ,递归深度最大为 \(|V|\) ,因此使用 \(O(|V|)\) 空间。

欢迎在评论区留下你的见解、问题或建议