跳轉至

9.3   圖的走訪

樹代表的是“一對多”的關係，而圖則具有更高的自由度，可以表示任意的“多對多”關係。因此，我們可以把樹看作圖的一種特例。顯然，樹的走訪操作也是圖的走訪操作的一種特例。

圖和樹都需要應用搜索演算法來實現走訪操作。圖的走訪方式也可分為兩種：廣度優先走訪和深度優先走訪。

9.3.1   廣度優先走訪

廣度優先走訪是一種由近及遠的走訪方式，從某個節點出發，始終優先訪問距離最近的頂點，並一層層向外擴張。如圖 9-9 所示，從左上角頂點出發，首先走訪該頂點的所有鄰接頂點，然後走訪下一個頂點的所有鄰接頂點，以此類推，直至所有頂點訪問完畢。

圖的廣度優先走訪

圖 9-9   圖的廣度優先走訪

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 !que.is_empty() {
        let vet = que.pop_front().unwrap(); // 佇列首頂點出隊
        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
graph_bfs.zig
[class]{}-[func]{graphBFS}
視覺化執行

程式碼相對抽象，建議對照圖 9-10 來加深理解。

圖的廣度優先走訪步驟

graph_bfs_step2

graph_bfs_step3

graph_bfs_step4

graph_bfs_step5

graph_bfs_step6

graph_bfs_step7

graph_bfs_step8

graph_bfs_step9

graph_bfs_step10

graph_bfs_step11

圖 9-10   圖的廣度優先走訪步驟

廣度優先走訪的序列是否唯一？

不唯一。廣度優先走訪只要求按“由近及遠”的順序走訪，而多個相同距離的頂點的走訪順序允許被任意打亂。以圖 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   圖的深度優先走訪

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
graph_dfs.zig
[class]{}-[func]{dfs}

[class]{}-[func]{graphDFS}
視覺化執行

深度優先走訪的演算法流程如圖 9-12 所示。

  • 直虛線代表向下遞推，表示開啟了一個新的遞迴方法來訪問新頂點。
  • 曲虛線代表向上回溯，表示此遞迴方法已經返回，回溯到了開啟此方法的位置。

為了加深理解，建議將圖 9-12 與程式碼結合起來，在腦中模擬（或者用筆畫下來）整個 DFS 過程，包括每個遞迴方法何時開啟、何時返回。

圖的深度優先走訪步驟

graph_dfs_step2

graph_dfs_step3

graph_dfs_step4

graph_dfs_step5

graph_dfs_step6

graph_dfs_step7

graph_dfs_step8

graph_dfs_step9

graph_dfs_step10

graph_dfs_step11

圖 9-12   圖的深度優先走訪步驟

深度優先走訪的序列是否唯一？

與廣度優先走訪類似，深度優先走訪序列的順序也不是唯一的。給定某頂點，先往哪個方向探索都可以，即鄰接頂點的順序可以任意打亂，都是深度優先走訪。

以樹的走訪為例，“根 \(\rightarrow\) 左 \(\rightarrow\) 右”“左 \(\rightarrow\) 根 \(\rightarrow\) 右”“左 \(\rightarrow\) 右 \(\rightarrow\) 根”分別對應前序、中序、後序走訪，它們展示了三種走訪優先順序，然而這三者都屬於深度優先走訪。

2.   複雜度分析

時間複雜度：所有頂點都會被訪問 \(1\) 次，使用 \(O(|V|)\) 時間；所有邊都會被訪問 \(2\) 次，使用 \(O(2|E|)\) 時間；總體使用 \(O(|V| + |E|)\) 時間。

空間複雜度：串列 res ，雜湊集合 visited 頂點數量最多為 \(|V|\) ，遞迴深度最大為 \(|V|\) ，因此使用 \(O(|V|)\) 空間。