C++ 數據結構：判斷有向圖中是否存在路徑的 DFS 與 BFS 實現

前言

在圖論與數據結構的學習中，判斷有向圖中兩個頂點之間是否存在路徑是一項基礎且重要的任務。本文將基於鄰接表存儲結構，詳細講解如何利用深度優先搜索（DFS）與廣度優先搜索（BFS）兩種經典遍歷算法來解決此問題，並提供核心思路與代碼實現要點。

核心思路

無論是 DFS 還是 BFS，核心邏輯一致：從起始頂點 Vi 出發，系統地遍歷圖中所有可達頂點。若在遍歷過程中訪問到了目標頂點 Vj，則證明路徑存在；反之，若遍歷結束仍未遇到 Vj，則路徑不存在。

深度優先搜索（DFS）

DFS 採用「走到黑，撞牆回退」的策略。實現時通常借助遞歸或顯式棧（Stack）來記錄路徑。對於路徑記錄需求，棧結構天然適合：進入一個頂點時入棧，回溯時出棧，最終棧中保存的即為從 Vi 到 Vj 的一條路徑。

廣度優先搜索（BFS）

BFS 採用「層層推進」的策略，借助佇列（Queue）實現。它優先探索距離起點較近的頂點，因此找到的路徑往往是「最短路徑」（以邊數計）。同樣，可通過維護前驅數組來重構路徑。

算法步驟概述

1. 初始化訪問標記數組 visited[]，所有頂點標記為未訪問。
2. 從 Vi 開始，執行 DFS 或 BFS 遍歷。
3. 遍歷過程中，若發現 Vj 已被訪問，立即返回 true（存在路徑）。
4. 遍歷結束仍未發現 Vj，返回 false（不存在路徑）。

代碼實現關鍵點（偽代碼）

// DFS 遞歸版
bool DFS(Graph G, int v, int target) {
    visited[v] = true;
    if (v == target) return true;
    for (each neighbor w of v) {
        if (!visited[w]) {
            if (DFS(G, w, target)) return true;
        }
    }
    return false;
}

// BFS 迭代版
bool BFS(Graph G, int start, int target) {
    Queue q;
    visited[start] = true;
    q.push(start);
    while (!q.empty()) {
        int v = q.front(); q.pop();
        if (v == target) return true;
        for (each neighbor w of v) {
            if (!visited[w]) {
                visited[w] = true;
                q.push(w);
            }
        }
    }
    return false;
}

總結

DFS 實現簡潔，適合路徑記錄；BFS 能找到最短路徑，適合無權圖的最短路問題。根據具體需求選擇即可。掌握這兩種遍歷模式，是解決圖論諸多問題（如連通性、拓撲排序、環檢測）的基石。