跳轉至

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|)\) 空間。

歡迎在評論區留下你的見解、問題或建議