C++ 圖論實戰二：DFS 與 BFS 完整實現、模板化設計與測試驗證

圖的儲存抽象：模板化支援多種儲存策略

template
class Network {
public:
    using VertexRef = Vertex&;
    using ConstVertexRef = const Vertex&;
    Network() = default;
    explicit Network(Weight no_edge) : storage_(no_edge) {}
    bool insertV(ConstVertexRef v) { return storage_.insertV(v); }
    bool insertE(ConstVertexRef u, ConstVertexRef v, Weight w) { return storage_.insertE(u, v, w); }
    ConstVertexRef getV(size_t idx) const { return storage_.getV(idx); }
    size_t nextV(size_t from, size_t prev = npos) const { return storage_.nextV(from, prev); }
    size_t vNum() const { return storage_.vNum(); }
    size_t eNum() const { return storage_.eNum(); }
    // DFS / BFS 介面
    template
    void DFS(Visit visit = Print) { dfs_impl(visit); }
    template
    void BFS(Visit visit = Print) { bfs_impl(visit); }
private:
    Storage storage_;
    std::vector visited_;
    static constexpr size_t npos = static_cast(-1);
    template
    void dfs_impl(Visit visit) {
        visited_.assign(vNum(), false);
        if (vNum()) dfs_recursive(0, visit);
    }
    template
    void dfs_recursive(size_t idx, Visit visit) {
        visit(getV(idx));
        visited_[idx] = true;
        for (size_t n = nextV(idx); n != npos; n = nextV(idx, n)) {
            if (!visited_[n]) dfs_recursive(n, visit);
        }
    }
    template
    void bfs_impl(Visit visit) {
        visited_.assign(vNum(), false);
        std::queue q;
        if (vNum()) {
            visited_[0] = true;
            q.push(0);
        }
        while (!q.empty()) {
            size_t cur = q.front(); q.pop();
            visit(getV(cur));
            for (size_t n = nextV(cur); n != npos; n = nextV(cur, n)) {
                if (!visited_[n]) {
                    visited_[n] = true;
                    q.push(n);
                }
            }
        }
    }
    template
    static void Print(ConstVertexRef v) { std::cout << v << ' '; }
};

兩種儲存策略實現

鄰接矩陣

template
class AdjMatrix {
    std::vector vertices_;
    std::vector> matrix_;
    Weight no_edge_;
public:
    explicit AdjMatrix(Weight no_edge) : no_edge_(no_edge) {}
    bool insertV(ConstVertexRef v) {
        vertices_.push_back(v);
        for (auto& row : matrix_) row.push_back(no_edge_);
        matrix_.emplace_back(vertices_.size(), no_edge_);
        return true;
    }
    bool insertE(ConstVertexRef u, ConstVertexRef v, Weight w) {
        auto iu = find_idx(u), iv = find_idx(v);
        if (iu == npos || iv == npos) return false;
        matrix_[iu][iv] = w;
        return true;
    }
    // getV, nextV, vNum, eNum 實現略...
};

鄰接表

template
struct Edge { Vertex to; Weight w; size_t next; };
template
class AdjList {
    std::vector vertices_;
    std::vector> edges_;
    std::vector head_;
    Weight no_edge_;
public:
    explicit AdjList(Weight no_edge) : no_edge_(no_edge) {}
    bool insertV(ConstVertexRef v) {
        vertices_.push_back(v);
        head_.push_back(npos);
        return true;
    }
    bool insertE(ConstVertexRef u, ConstVertexRef v, Weight w) {
        auto iu = find_idx(u), iv = find_idx(v);
        if (iu == npos || iv == npos) return false;
        edges_.push_back({v, w, head_[iu]});
        head_[iu] = edges_.size() - 1;
        return true;
    }
    // getV, nextV (遍歷 edges_[head_[idx]] 鏈表), vNum, eNum 實現略...
};

測試驗證

int main() {
    using Graph = Network>;
    Graph g(INT_MAX); // 無邊權重用 INT_MAX
    g.insertV('A'); g.insertV('B'); g.insertV('C'); g.insertV('D');
    g.insertE('A', 'B', 1);
    g.insertE('A', 'C', 2);
    g.insertE('B', 'D', 3);
    std::cout << "DFS: "; g.DFS(); std::cout << '\n'; // 預期: A B D C (或 A C B D 視插入順序)
    std::cout << "BFS: "; g.BFS(); std::cout << '\n'; // 預期: A B C D
    return 0;
}

關鍵設計決策解析

1. 三參數模板：`Vertex`、`Weight`、`Storage` 解耦 **資料型別**、**權重型別**、**儲存策略** — 單一類別支援 8 種組合 (有向/無向 × 帶權/不帶權 × 矩陣/表)，避免多重繼承菱形災難。
2. 訪問器模式：`DFS`/`BFS` 接受可調用物件 `Visit`，**演算法與處理邏輯分離**，支援列印、收集、檢查、序列化等任意操作。
3. 迭代式 BFS：`std::queue` 替代遞迴，避免深圖棧溢出，效能更穩定。
4. 訪問標記 `vector`**：隨圖大小動態分配，每次遍歷重置，記憶體效率高。
5. `npos` 哨兵**：`static_cast(-1)` 表示無後續頂點，避免魔術數字。

擴展方向

• **無向圖**：`insertE` 雙向插入，或儲存層提供 `undirected` 標記。
• **最小生成樹**：Prim/Kruskal，需優先隊列 + 並查集。
• **最短路徑**：Dijkstra (非負權)、Bellman-Ford (負權)、Floyd-Warshall (全對)。
• **拓撲排序 / 關鍵路徑 (AOV/AOE)**：Kahn 算法 / DFS 後序逆序。
• **強連通分量**：Kosaraju / Tarjan。
• **圖神經網絡特徵提取**：鄰接矩陣歸一化 + 稀疏矩陣乘法 (PyG/DGL 風格)。

效能對比參考

結語

**模板化儲存策略 + 訪問器演算法** 是 C++ 實現圖庫的經典範式。**避免多重繼承，採用策略模式 (Policy-based Design)**，既獲得零開銷抽象，又保持程式碼清晰可維護。下一步將實現 MST、最短路徑、拓撲排序，敬請期待。