图数据结构详解：存储结构、遍历与核心算法

邻接表

邻接表使用数组表示顶点集合，链表表示边的关系。适合稀疏图，查找一个顶点连接的边效率高，但不易判断两顶点是否相连。

namespace link_table {
template<class W>
struct Edge {
    int _dsti;
    W _w;
    Edge<W>* _next;
    Edge(int dsti, const W& w) :_dsti(dsti), _w(w), _next(nullptr) {}
};

template<class V, class W, bool Direction = false>
class Graph {
typedef Edge<W> Edge;
public:
    Graph(const V* a, size_t n) {
        _vertexs.reserve(n);
        for (size_t i = 0; i < n; ++i) {
            _vertexs.push_back(a[i]);
            _indexMap[a[i]] = i;
        }
        _tables.resize(n, nullptr);
    }

    void AddEdge(const V& src, const V& dst, const W& w) {
        size_t srci = GetVertexIndex(src);
        size_t dsti = GetVertexIndex(dst);
        Edge* eg = new Edge(dsti, w);
        eg->_next = _tables[srci];
        _tables[srci] = eg;
        if (!Direction) {
            Edge* eg2 = new Edge(srci, w);
            eg2->_next = _tables[dsti];
            _tables[dsti] = eg2;
        }
    }

    void Print() {
        for (size_t i = 0; i < _vertexs.size(); ++i)
            cout << _vertexs[i] << "[" << i << "] -> ";
        Edge* cur = _tables[i];
        while (cur) {
            cout << "[" << _vertexs[cur->_dsti] << ":" << cur->_w << "] -> ";
            cur = cur->_next;
        }
        cout << "nullptr" << endl;
    }
private:
    vector<V> _vertexs;
    map<V, int> _indexMap;
    vector<Edge*> _tables;
};
}

图的遍历

广度优先遍历 (BFS)

BFS 类似树的层序遍历，使用队列实现。每次访问当前顶点的所有未访问邻接点。

void BFS(const V& src) {
    size_t srci = GetVertexIndex(src);
    queue<int> q;
    vector<bool> visited(_vertexs.size(), false);
    q.push(srci);
    visited[srci] = true;
    int levelSize = 1;
    size_t n = _vertexs.size();
    while (!q.empty()) {
        for (int i = 0; i < levelSize; ++i) {
            int front = q.front(); q.pop();
            cout << front << ":" << _vertexs[front] << " ";
            for (size_t j = 0; j < n; ++j) {
                if (_matrix[front][j] != MAX_W && !visited[j]) {
                    q.push(j); visited[j] = true;
                }
            }
        }
        cout << endl;
        levelSize = q.size();
    }
}

深度优先遍历 (DFS)

DFS 类似树的先序遍历，使用递归或栈实现。访问一个顶点后，立即深入其第一个未访问邻接点。

void _DFS(size_t srci, vector<bool>& visited) {
    cout << srci << ":" << _vertexs[srci] << endl;
    visited[srci] = true;
    for (size_t i = 0; i < _vertexs.size(); ++i) {
        if (_matrix[srci][i] != MAX_W && !visited[i])
            _DFS(i, visited);
    }
}

void DFS(const V& src) {
    size_t srci = GetVertexIndex(src);
    vector<bool> visited(_vertexs.size(), false);
    _DFS(srci, visited);
}

最小生成树

连通图的生成树包含所有顶点且无环，边数为 n-1。构造准则：只使用图中边、恰好 n-1 条边、不构成回路。

Kruskal 算法

Kruskal 算法基于并查集。将所有边按权值排序，依次选取不构成回路的边加入生成树。

struct Edge {
    size_t _srci, _dsti;
    W _w;
    Edge(size_t s, size_t d, const W& w) :_srci(s), _dsti(d), _w(w) {}
    bool operator>(const Edge& e) const { return _w > e._w; }
};

W Kruskal(Self& minTree) {
    priority_queue<Edge, vector<Edge>, greater<Edge>> minque;
    // 收集所有边
    for (size_t i = 0; i < n; ++i)
        for (size_t j = i + 1; j < n; ++j)
            if (_matrix[i][j] != MAX_W)
                minque.push(Edge(i, j, _matrix[i][j]));

    UnionFindSet ufs(n);
    int size = 0; W totalW = W();
    while (!minque.empty()) {
        Edge min = minque.top(); minque.pop();
        if (!ufs.InSet(min._srci, min._dsti)) {
            minTree._AddEdge(min._srci, min._dsti, min._w);
            ufs.Union(min._srci, min._dsti);
            totalW += min._w; ++size;
        }
    }
    return (size == n - 1) ? totalW : W();
}

Prim 算法

Prim 算法从指定起点开始，维护已选顶点集 X 和未选顶点集 Y，不断选择连接 X 和 Y 的最小权边。

W Prim(Self& minTree, const V& src) {
    size_t srci = GetVertexIndex(src);
    size_t n = _vertexs.size();
    vector<bool> X(n, false), Y(n, true);
    X[srci] = true; Y[srci] = false;
    priority_queue<Edge, vector<Edge>, greater<Edge>> minq;
    for (size_t i = 0; i < n; ++i)
        if (_matrix[srci][i] != MAX_W)
            minq.push(Edge(srci, i, _matrix[srci][i]));

    int size = 0; W totalW = W();
    while (!minq.empty()) {
        Edge min = minq.top(); minq.pop();
        if (!X[min._dsti]) {
            minTree._AddEdge(min._srci, min._dsti, min._w);
            X[min._dsti] = true; Y[min._dsti] = false;
            totalW += min._w; ++size;
            if (size == n - 1) break;
            for (size_t i = 0; i < n; ++i)
                if (_matrix[min._dsti][i] != MAX_W && Y[i])
                    minq.push(Edge(min._dsti, i, _matrix[min._dsti][i]));
        }
    }
    return (size == n - 1) ? totalW : W();
}

最短路径

Dijkstra 算法

解决单源最短路径问题，要求边权非负。采用贪心策略，每次从未确定集合中选出距离最小的点更新邻居。

void Dijkstra(const V& src, vector<W>& dist, vector<int>& pPath) {
    size_t srci = GetVertexIndex(src);
    size_t n = _vertexs.size();
    dist.assign(n, MAX_W); pPath.assign(n, -1);
    dist[srci] = 0; pPath[srci] = srci;
    vector<bool> S(n, false);
    for (size_t j = 0; j < n; ++j) {
        int u = 0; W min = MAX_W;
        for (size_t i = 0; i < n; ++i)
            if (!S[i] && dist[i] < min) { u = i; min = dist[i]; }
        S[u] = true;
        for (size_t v = 0; v < n; ++v)
            if (!S[v] && _matrix[u][v] != MAX_W && dist[u] + _matrix[u][v] < dist[v]) {
                dist[v] = dist[u] + _matrix[u][v];
                pPath[v] = u;
            }
    }
}

Bellman-Ford 算法

可处理负权边，并能检测负权回路。通过松弛操作迭代更新，时间复杂度 O(N*E)。

bool BellmanFord(const V& src, vector<W>& dist, vector<int>& pPath) {
    size_t srci = GetVertexIndex(src);
    size_t n = _vertexs.size();
    dist.assign(n, MAX_W); pPath.assign(n, -1);
    dist[srci] = W();
    for (size_t k = 0; k < n; ++k) {
        bool updata = false;
        for (size_t i = 0; i < n; ++i)
            for (size_t j = 0; j < n; ++j)
                if (_matrix[i][j] != MAX_W && dist[i] + _matrix[i][j] < dist[j]) {
                    dist[j] = dist[i] + _matrix[i][j];
                    pPath[j] = i; updata = true;
                }
        if (!updata) break;
    }
    for (size_t i = 0; i < n; ++i)
        for (size_t j = 0; j < n; ++j)
            if (_matrix[i][j] != MAX_W && dist[i] + _matrix[i][j] < dist[j])
                return false;
    return true;
}

Floyd-Warshall 算法

多源最短路径算法，本质是动态规划。D[i][j][k] 表示经过前 k 个点的最短路径，可优化为三维转二维。

void FloydWarShall(vector<vector<W>>& vvDist, vector<vector<int>>& vvpPath) {
    size_t n = _vertexs.size();
    vvDist.assign(n, vector<W>(n, MAX_W));
    vvpPath.assign(n, vector<int>(n, -1));
    for (size_t i = 0; i < n; ++i)
        for (size_t j = 0; j < n; ++j)
            if (_matrix[i][j] != MAX_W) {
                vvDist[i][j] = _matrix[i][j];
                vvpPath[i][j] = i;
            }
    for (size_t k = 0; k < n; ++k)
        for (size_t i = 0; i < n; ++i)
            for (size_t j = 0; j < n; ++j)
                if (vvDist[i][k] != MAX_W && vvDist[k][j] != MAX_W &&
                    vvDist[i][k] + vvDist[k][j] < vvDist[i][j]) {
                    vvDist[i][j] = vvDist[i][k] + vvDist[k][j];
                    vvpPath[i][j] = vvpPath[k][j];
                }
}

整体实现

以下是完整的头文件结构与测试入口，整合了上述所有功能。

UnionFindSet.h

#pragma once
#include<vector>
class UnionFindSet {
public:
    UnionFindSet(size_t n) :_ufs(n, -1) {}
    int FindRoot(int x) {
        int root = x;
        while (_ufs[root] >= 0) root = _ufs[root];
        while (_ufs[x] >= 0) { int parent = _ufs[x]; _ufs[x] = root; x = parent; }
        return root;
    }
    bool Union(int x1, int x2) {
        int root1 = FindRoot(x1), root2 = FindRoot(x2);
        if (root1 == root2) return false;
        if (abs(_ufs[root1]) < abs(_ufs[root2])) swap(root1, root2);
        _ufs[root1] += _ufs[root2]; _ufs[root2] = root1;
        return true;
    }
    bool InSet(int x1, int x2) { return FindRoot(x1) == FindRoot(x2); }
private:
    vector<int> _ufs;
};

Graph.h

（此处省略重复的类定义，参考上文各章节中的 Graph 类实现）

test.cpp

#include<iostream>
using namespace std;
#include"UnionFindSet.h"
#include"Graph.h"

int main() {
    // 示例：Floyd 算法测试
    const char* str = "12345";
    Graph<char, int, INT_MAX, true> g(str, strlen(str));
    g.AddEdge('1', '2', 3); g.AddEdge('1', '3', 8); g.AddEdge('1', '5', -4);
    g.AddEdge('2', '4', 1); g.AddEdge('2', '5', 7); g.AddEdge('3', '2', 4);
    g.AddEdge('4', '1', 2); g.AddEdge('4', '3', -5); g.AddEdge('5', '4', 6);

    vector<vector<int>> vvDist, vvParentPath;
    g.FloydWarShall(vvDist, vvParentPath);

    for (size_t i = 0; i < strlen(str); ++i)
        g.PrintShortPath(str[i], vvDist[i], vvParentPath[i]);

    return 0;
}