C++ 数据结构之图：从理论到实践

一、图的基本概念

1.1 图的定义与组成

图（Graph）由顶点（Vertex）和边（Edge）组成，形式化定义为：

G = (V, E)

• 顶点集合 V：表示实体（如城市、用户）

• 边集合 E：表示实体间关系（如道路、社交关系）

1.2 图的分类

二、图的存储结构

2.1 邻接矩阵

使用二维数组存储顶点间关系

class AdjMatrixGraph {
private:
    vector<vector<int>> matrix;  // 存储边权
    int vertexCount;

public:
    AdjMatrixGraph(int n) : vertexCount(n), matrix(n, vector<int>(n, 0)) {}

    void addEdge(int from, int to, int weight = 1) {
        matrix[from][to] = weight;
        // 无向图需添加 matrix[to][from] = weight;
    }

    void print() {
        for (auto& row : matrix) {
            for (int val : row) cout << val << " ";
            cout << endl;
        }
    }
};

特点：

• 空间复杂度 O(V²)

• 适合稠密图

• 快速判断顶点是否邻接

2.2 邻接表

使用链表/数组存储邻接关系

struct EdgeNode {
    int dest;
    int weight;
    EdgeNode* next;
};

class AdjListGraph {
private:
    struct VertexNode {
        EdgeNode* head = nullptr;
    };

    vector<VertexNode> vertices;
    int vertexCount;

public:
    AdjListGraph(int n) : vertexCount(n), vertices(n) {}

    void addEdge(int from, int to, int weight = 1) {
        EdgeNode* newNode = new EdgeNode{to, weight, vertices[from].head};
        vertices[from].head = newNode;
    }

    ~AdjListGraph() {
        for (auto& v : vertices) {
            while (v.head) {
                EdgeNode* temp = v.head;
                v.head = v.head->next;
                delete temp;
            }
        }
    }
};

特点：

• 空间复杂度 O(V + E)

• 适合稀疏图

• 高效遍历邻接顶点

三、图的遍历算法

3.1 深度优先搜索（DFS）

void dfs(const AdjListGraph& graph, int v, vector<bool>& visited) {
    visited[v] = true;
    cout << "Visit: " << v << endl;

    EdgeNode* curr = graph.getEdges(v);
    while (curr) {
        if (!visited[curr->dest]) {
            dfs(graph, curr->dest, visited);
        }
        curr = curr->next;
    }
}

3.2 广度优先搜索（BFS）

void bfs(const AdjListGraph& graph, int start) {
    vector<bool> visited(graph.size(), false);
    queue<int> q;

    visited[start] = true;
    q.push(start);

    while (!q.empty()) {
        int v = q.front();
        q.pop();
        cout << "Visit: " << v << endl;

        EdgeNode* curr = graph.getEdges(v);
        while (curr) {
            if (!visited[curr->dest]) {
                visited[curr->dest] = true;
                q.push(curr->dest);
            }
            curr = curr->next;
        }
    }
}

四、经典图算法实现

4.1 Dijkstra 最短路径算法

vector<int> dijkstra(const AdjListGraph& graph, int src) {
    const int INF = INT_MAX;
    vector<int> dist(graph.size(), INF);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;

    dist[src] = 0;
    pq.emplace(0, src);

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();

        if (d > dist[u]) continue;

        EdgeNode* curr = graph.getEdges(u);
        while (curr) {
            int v = curr->dest;
            int w = curr->weight;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.emplace(dist[v], v);
            }
            curr = curr->next;
        }
    }
    return dist;
}

4.2 Prim 最小生成树算法

int primMST(const AdjListGraph& graph) {
    const int INF = INT_MAX;
    vector<int> key(graph.size(), INF);
    vector<bool> inMST(graph.size(), false);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;

    key[0] = 0;
    pq.emplace(0, 0);
    int totalWeight = 0;

    while (!pq.empty()) {
        auto [k, u] = pq.top();
        pq.pop();

        if (inMST[u]) continue;
        inMST[u] = true;
        totalWeight += k;

        EdgeNode* curr = graph.getEdges(u);
        while (curr) {
            int v = curr->dest;
            int w = curr->weight;
            if (!inMST[v] && w < key[v]) {
                key[v] = w;
                pq.emplace(key[v], v);
            }
            curr = curr->next;
        }
    }
    return totalWeight;
}

五、图的应用场景

5.1 社交网络分析

• 顶点：用户

• 边：关注/好友关系

• 算法应用：推荐系统（BFS扩展好友）、影响力分析（PageRank）

5.2 路径规划系统

• 顶点：地点

• 边：道路（权重=距离/时间）

• 算法应用：最短路径（Dijkstra）、实时导航（A*算法）

5.3 任务调度系统

• 顶点：任务

• 边：依赖关系（有向边）

• 算法应用：拓扑排序检测循环依赖

六、性能优化技巧

6.1 数据结构选择策略

6.2 内存管理优化

// 使用智能指针管理边节点
class SafeAdjListGraph {
private:
    struct EdgeNode {
        int dest;
        shared_ptr<EdgeNode> next;
    };

    vector<shared_ptr<EdgeNode>> vertices;
};

6.3 并行计算优化

// 使用OpenMP并行处理边
void parallelBFS(const AdjListGraph& graph, int start) {
    // ...
    #pragma omp parallel for
    for (EdgeNode* curr = graph.getEdges(u); curr; curr = curr->next) {
        // 并行处理邻接节点
    }
}

七、现代C++图实现示例

template <typename VertexType, typename EdgeType = int>
class Graph {
private:
    unordered_map<VertexType, list<pair<VertexType, EdgeType>>> adjList;

public:
    void addVertex(const VertexType& v) {
        adjList.emplace(v, list<pair<VertexType, EdgeType>>());
    }

    void addEdge(const VertexType& from, const VertexType& to, EdgeType weight = 1) {
        adjList[from].emplace_back(to, weight);
    }

    auto dijkstra(const VertexType& start) -> unordered_map<VertexType, EdgeType> {
        // 实现Dijkstra算法...
    }

    // 其他算法实现...
};

// 使用示例
Graph<string> cityGraph;
cityGraph.addVertex("Beijing");
cityGraph.addVertex("Shanghai");
cityGraph.addEdge("Beijing", "Shanghai", 1200); // 公里数

八、总结与学习资源

8.1 关键要点

1. 存储结构选择：根据场景选择矩阵或邻接表

2. 算法复杂度认知：DFS/BFS O(V+E)，Dijkstra O(E log V)

3. 现代C++实践：使用STL容器和智能指针

4. 性能优化方向：并行处理、内存布局优化

8.2 推荐学习路径

1. 基础理论：《算法导论》图论章节

2. 算法可视化：VisuAlgo.net 图算法演示

3. 高性能实现：Boost Graph Library (BGL)

4. 领域应用：社交网络分析、推荐系统论文

“图是描述复杂关系的终极工具——从微小的分子结构到浩瀚的宇宙网络，皆可用图建模。” —— 匿名算法工程师

通过掌握图的存储结构与经典算法，开发者可以解锁解决复杂系统问题的能力。建议结合具体应用场景进行实践，逐步深入理解这一强大的数据结构。