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 数据结构选择策略

图类型	推荐存储结构	理由
稠密图	邻接矩阵	快速访问任意边
稀疏图	邻接表	节省内存
动态变化图	邻接表	高效增删边操作
需要频繁判断邻接	邻接矩阵	O(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 forfor (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. 领域应用：社交网络分析、推荐系统论文

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

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