C++ 圖結構完整實現：鄰接表、BFS/DFS、拓撲排序、Bellman-Ford

本文整理自 GitHub 開源項目 obscure76/graph，展示一個功能完整的 C++ 圖類實現，涵蓋頂點/邊封裝、鄰接表存儲、BFS/DFS 遍歷、路徑和查找、拓撲排序、Bellman-Ford 最短路徑等核心演算法，代碼結構清晰，適合學習圖論與 C++ STL 綜合應用。

類設計總覽

核心資料結構

class Graph {
    map<int, list<int>> vertices; // 頂點ID -> 鄰接頂點列表
    list<Edge> edges;               // 邊集合（帶權）
    set<int> visited;               // 遍歷標記
public:
    bool addVertex(int v);
    bool addEdge(int wt, int src, int dst);
    void print();                   // 打印鄰接表
    void bfs();                     // 廣度優先搜索
    void dfstraversal();            // 深度優先遍歷
    void dfs(int v, list<int> adj); // DFS 遞歸輔助
    void pathSum(int sum);          // 查找路徑權重和為 sum 的路徑
    void findpath(int sum, int cval, char* str, int in, int curr); // 遞歸查找
    void bellman();                 // Bellman-Ford 最短路徑
    list<int> topologicalSort();    // 拓撲排序 (Kahn/DFS)
    void topo();                    // 輔助
};

關鍵演算法實現節選

BFS 迭代實現

void Graph::bfs() {
    queue<int> q;
    visited.clear();
    q.push(vertices.begin()->first);
    visited.insert(vertices.begin()->first);
    while (!q.empty()) {
        int v = q.front(); q.pop();
        for (int nxt : vertices[v]) {
            if (visited.count(nxt)) continue;
            visited.insert(nxt);
            q.push(nxt);
        }
        cout << v << ' ';
    }
}

DFS 遞歸 + 拓撲排序

void Graph::dfs(int v, list<int> adj) {
    for (int nxt : adj) {
        if (visited.count(nxt)) continue;
        visited.insert(nxt);
        dfs(nxt, vertices[nxt]);
    }
    cout << v << ' ';
    order.push_front(v); // 後序入棧 → 拓撲序
}
list<int> Graph::topologicalSort() {
    order.clear();
    dfstraversal(); // 內部調用 dfs 填充 order
    return order;
}

Bellman-Ford（基於拓撲序優化的 DAG 最短路徑）

void Graph::bellman() {
    order.clear(); dfstraversal(); // 先獲取拓撲序
    map<int, int> dist;
    for (auto& v : vertices) dist[v.first] = INT_MAX;
    dist[vertices.begin()->first] = 0;

    for (int v : order) { // 按拓撲序鬆弛
        for (auto& e : edges) {
            if (e.getSource() != v) continue;
            int u = e.getDest(), w = e.getWeight();
            if (dist[u] > dist[v] + w) dist[u] = dist[v] + w;
        }
    }
    for (auto& d : dist) cout << d.first << " at dist " << d.second << endl;
}

主程式測試案例

int main() {
    Graph g;
    g.addEdge(1, 1, 2); g.addEdge(1, 1, 3);
    g.addEdge(1, 2, 4); g.addEdge(1, 2, 5);
    g.addEdge(1, 3, 6); g.addEdge(1, 3, 8);
    g.print();           // 打印鄰接表
    g.bfs();             // BFS 遍歷
    g.dfstraversal();    // DFS 遍歷
    g.pathSum(8);        // 路徑和為 8 的路徑
    g.topologicalSort(); // 拓撲序
    g.bellman();         // 最短路徑
    return 0;
}

代碼亮點與不足

• ✅ 使用 STL map/list/set/queue 現代化實現
• ✅ 頂點/邊/圖三層封裝，職責清晰
• ✅ 同時支援無權/有權、有向/無向（邊雙向添加即可）
• ⚠️ Vertex 類內部 pair 設計略顯生硬，可改為獨立成員
• ⚠️ pathSum 使用 char* 手動內存管理，建議改用 std::string
• ⚠️ 缺少 Dijkstra、Floyd-Warshall、強連通分量等進階演算法

擴展建議

1. 引入 std::unordered_map 提升稠密圖查找效能
2. 模板化頂點/邊權重類型
3. 增加迭代器介面，支援範圍 for 遍歷
4. 補全單元測試與效能基準

這份代碼是學習「C++ 實現圖論演算法」的優秀起點，建議在理解基礎上重構為更符合現代 C++ 風格的庫。