您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

C++ 數據結構進階：圖的存儲、遍歷與核心算法完整實現

編輯：關於C++

圖是應用最廣泛的數據結構，其核心在算法而非存儲。本文實現圖的兩種主流存儲（鄰接矩陣、鏈接表），並詳細講解 DFS/BFS 遍歷、最小生成樹（Prim/Kruskal）、最短路徑（Floyd/Dijkstra/A*）、拓撲排序與關鍵路徑等核心算法，代碼採用模板泛型設計，存儲與算法解耦。

圖的基本存儲結構

1. 鄰接矩陣

適用稠密圖。使用二維數組 edge[i][j] 存儲邊權值，NoEdge 表示無邊。

template <class name, class dist>
class AdjMatrix {
    name *vertex; dist **edge; int vNum, eNum; dist NoEdge;
    // insertV, insertE, getV, nextV, find...
};

2. 鏈接表

適用稀疏圖。每個頂點維護一個 list<edge> 存儲出邊。

struct edge { int vID; dist cost; };
struct vertex { name v; list<edge> *e; };
vector<vertex> vertices;

統一網絡介面：Network 模板類

以存儲策略為模板參數，實現邏輯與存儲分離：

template <class name, class dist, class mem>
class Network {
    mem data; // AdjMatrix 或 LinkedList
    // 統一介面：insertV, insertE, getV, nextV, vNum, eNum...
};

遍歷算法：DFS 與 BFS

圖可能有回路，必須標記訪問過的頂點。

深度優先搜索 (DFS)

void DFS(void(*visit)(name)=print) {
    visited = new bool[vNum()]; fill_n(visited, vNum(), false);
    DFS(0, visit); delete[] visited;
}
void DFS(int i, void(*visit)(name)) {
    visit(getV(i)); visited[i] = true;
    for (int n = nextV(i); n != -1; n = nextV(i, n))
        if (!visited[n]) DFS(n, visit);
}

廣度優先搜索 (BFS)

void BFS(int i=0, void(*visit)(name)=print) {
    visited = new bool[vNum()]; fill_n(visited, vNum(), false);
    queue<int> q; visited[i] = true;
    while (i != -1) {
        visit(getV(i));
        for (int n = nextV(i); n != -1; n = nextV(i, n))
            if (!visited[n]) { q.push(n); visited[n] = true; }
        if (q.empty()) break;
        i = q.front(); q.pop();
    }
    delete[] visited;
}

無向圖與連通分量

無向圖按有向圖存儲雙向邊。連通分量：對每個未訪問頂點調用 DFS。

void components() {
    visited = new bool[vNum()]; fill_n(visited, vNum(), false);
    for (int i=0, j=0; i<vNum(); i++)
        if (!visited[i]) { cout << '(' << ++j << ')'; DFS(i); cout << endl; }
    delete[] visited;
}

關節點（割點）算法

基於 DFS 生成樹，計算 dfn（訪問序號）與 low（子樹回邊能達到的最小 dfn）。根節點單獨判斷（子樹數>1），非根節點判斷 low[child] >= dfn[parent]。

最小生成樹 (MST)

儲存結構

template <class dist> struct MSTedge {
    int v1, v2; dist cost;
    bool operator<(const MSTedge& o) { return cost < o.cost; }
};

Kruskal 算法（邊集 + 並查集 + 最小堆）

適用稀疏圖（鏈接表存儲）。時間復雜度 O(E log E)。

int MinSpanTree(MSTedge<dist>* a) {
    MinHeap<MSTedge<dist>> E; MFSets V(vNum);
    // 所有邊入堆
    for (i=0; i<vNum; i++)
        for (iter=vertices[i].e->begin(); iter!=end; iter++)
            E.insert(MSTedge(i, iter->vID, iter->cost));
    // 選邊
    for (i=0; i<eNum && l<vNum; i++) {
        j = V.find(E.top().v1); k = V.find(E.top().v2);
        if (j != k) { V.merge(j,k); a[l++] = E.top(); }
        E.pop();
    }
    return l;
}

Prim 算法（頂點集 + 鄰接矩陣）

適用稠密圖。時間復雜度 O(V²)。

int MinSpanTree(MSTedge<dist>* a) {
    dist *lowC = new dist[vNum]; int *nearV = new int[vNum];
    for (i=0; i<vNum; i++) { lowC[i]=edge[0][i]; nearV[i]=0; } nearV[0]=-1;
    for (k=0; k<vNum-1; k++) {
        // 找最小邊
        for (i=1, j=0; i<vNum; i++)
            if (nearV[i]!=-1 && lowC[i]<lowC[j]) j=i;
        a[k] = MSTedge(nearV[j], j, lowC[j]); nearV[j]=-1;
        if (a[k].cost == NoEdge) return k-1;
        // 更新低成本
        for (i=1; i<vNum; i++)
            if (nearV[i]!=-1 && edge[i][j]<lowC[i])
                { lowC[i]=edge[i][j]; nearV[i]=j; }
    }
    return k;
}

最短路徑算法

採用獨立算法類 Weight 綁定圖對象，分離存儲與計算。

Floyd 算法（全對最短路徑，O(V³)）

void AllShortestPath() {
    for (k=0; k<N; k++) {
        shortest[k]=true;
        for (i=0; i<N; i++)
            for (j=0; j<N; j++)
                if (len[i][k]+len[k][j] < len[i][j]) {
                    len[i][j] = len[i][k]+len[k][j];
                    path[i][j] = path[k][j];
                }
    }
    all = true;
}

Dijkstra 算法（單源最短路徑，邊權非負，O(V²)）

void ShortestPath(name v1, name v2) {
    int s = find(v1), t = find(v2);
    bool *S = new bool[N](); S[s]=true;
    for (i=0; i<N-1; i++) {
        // 找未訪問最近頂點
        for (j=0, k=s; j<N; j++)
            if (!S[j] && len[s][j] < len[s][k]) k=j;
        S[k]=true;
        // 鬆弛
        for (j=0; j<N; j++)
            if (!S[j] && len[s][k]+len[k][j] < len[s][j]) {
                len[s][j] = len[s][k]+len[k][j];
                path[s][j] = k;
            }
    }
    shortest[s]=true; print(s,t);
}