《C++中的图论算法及其实现方法》
图论作为数学与计算机科学的交叉领域，在路径规划、网络分析、社交关系建模等场景中具有广泛应用。C++凭借其高效的性能和灵活的数据结构支持，成为实现图论算法的理想语言。本文将系统阐述图论基础概念，结合C++实现核心算法，并分析其应用场景与优化策略。
一、图论基础与数据结构表示
图由顶点（Vertex）和边（Edge）构成，分为有向图和无向图。根据边的权重，还可分为带权图和非带权图。在C++中，图的存储方式直接影响算法效率，常见方法包括邻接矩阵和邻接表。
1.1 邻接矩阵实现
邻接矩阵使用二维数组存储顶点间连接关系，适用于稠密图。其空间复杂度为O(V²)，其中V为顶点数。
#include
using namespace std;
class GraphMatrix {
private:
vector> matrix;
int vertexCount;
public:
GraphMatrix(int n) : vertexCount(n), matrix(n, vector(n, 0)) {}
void addEdge(int u, int v, int weight = 1) {
matrix[u][v] = weight;
// 无向图需添加 matrix[v][u] = weight;
}
bool hasEdge(int u, int v) {
return matrix[u][v] != 0;
}
}; 1.2 邻接表实现
邻接表通过链表或动态数组存储每个顶点的邻居，适用于稀疏图，空间复杂度为O(V+E)。
#include
#include
class GraphList {
private:
unordered_map>> adjList; // {顶点: [(邻居, 权重)]}
public:
void addEdge(int u, int v, int weight = 1) {
adjList[u].emplace_back(v, weight);
// 无向图需添加 adjList[v].emplace_back(u, weight);
}
const list>& getNeighbors(int u) {
return adjList[u];
}
};
二、核心图论算法实现
2.1 深度优先搜索（DFS）
DFS通过递归或栈实现，用于遍历或搜索图中的所有顶点，时间复杂度为O(V+E)。
#include
#include
void DFS(const GraphList& graph, int start) {
vector visited(graph.adjList.size(), false);
stack s;
s.push(start);
while (!s.empty()) {
int u = s.top();
s.pop();
if (!visited[u]) {
visited[u] = true;
cout 2.2 广度优先搜索（BFS）
BFS使用队列实现，适用于寻找最短路径（非带权图），时间复杂度为O(V+E)。
#include
void BFS(const GraphList& graph, int start) {
vector visited(graph.adjList.size(), false);
queue q;
q.push(start);
visited[start] = true;
while (!q.empty()) {
int u = q.front();
q.pop();
cout 2.3 Dijkstra算法（单源最短路径）
Dijkstra算法通过优先队列优化，解决带权有向图的单源最短路径问题，时间复杂度为O((V+E)logV)。
#include
#include
vector dijkstra(const GraphList& graph, int start) {
int n = graph.adjList.size();
vector dist(n, INT_MAX);
priority_queue, vector>, greater>> pq;
dist[start] = 0;
pq.emplace(0, start);
while (!pq.empty()) {
int u = pq.top().second;
pq.pop();
for (const auto& [v, weight] : graph.getNeighbors(u)) {
if (dist[v] > dist[u] + weight) {
dist[v] = dist[u] + weight;
pq.emplace(dist[v], v);
}
}
}
return dist;
} 2.4 Floyd-Warshall算法（多源最短路径）
Floyd-Warshall算法通过动态规划计算所有顶点对的最短路径，时间复杂度为O(V³)，适用于稠密图。
vector> floydWarshall(const GraphMatrix& graph) {
int n = graph.vertexCount;
vector> dist(n, vector(n, INT_MAX));
// 初始化距离矩阵
for (int i = 0; i dist[i][k] + dist[k][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
return dist;
} 2.5 Prim算法（最小生成树）
Prim算法通过贪心策略构建最小生成树，时间复杂度为O(ElogV)。
#include
vector> primMST(const GraphList& graph) {
int n = graph.adjList.size();
vector key(n, INT_MAX);
vector parent(n, -1);
vector inMST(n, false);
priority_queue, vector>, greater>> pq;
key[0] = 0;
pq.emplace(0, 0);
while (!pq.empty()) {
int u = pq.top().second;
pq.pop();
inMST[u] = true;
for (const auto& [v, weight] : graph.getNeighbors(u)) {
if (!inMST[v] && key[v] > weight) {
key[v] = weight;
parent[v] = u;
pq.emplace(key[v], v);
}
}
}
vector> mstEdges;
for (int i = 1; i 三、算法优化与应用场景
1. 稀疏图优化：邻接表比邻接矩阵更节省空间，适合顶点多但边少的场景。
2. 并行计算：BFS和Dijkstra算法可通过多线程加速，例如使用OpenMP并行处理邻居节点。
3. 实时系统：在导航系统中，A*算法结合启发式函数可进一步优化路径搜索效率。
4. 大规模图处理：分布式图计算框架（如GraphX）可处理亿级顶点图，但单机C++实现需关注内存管理。
四、完整案例：城市交通最短路径
以下代码整合Dijkstra算法与邻接表，模拟城市交通网络的最短路径查询。
#include
#include
#include
#include
#include
#include
using namespace std;
class CityGraph {
private:
unordered_map>> adjList;
public:
void addRoad(const string& u, const string& v, int distance) {
adjList[u].emplace_back(v, distance);
adjList[v].emplace_back(u, distance); // 无向图
}
unordered_map shortestPath(const string& start) {
unordered_map dist;
priority_queue, vector>, greater>> pq;
for (const auto& [city, _] : adjList) {
dist[city] = (city == start) ? 0 : INT_MAX;
pq.emplace(dist[city], city);
}
while (!pq.empty()) {
string u = pq.top().second;
pq.pop();
for (const auto& [v, weight] : adjList[u]) {
if (dist[v] > dist[u] + weight) {
dist[v] = dist[u] + weight;
pq.emplace(dist[v], v);
}
}
}
return dist;
}
};
int main() {
CityGraph g;
g.addRoad("A", "B", 4);
g.addRoad("A", "C", 2);
g.addRoad("B", "C", 1);
g.addRoad("B", "D", 5);
g.addRoad("C", "D", 8);
auto dist = g.shortestPath("A");
for (const auto& [city, d] : dist) {
cout
关键词
图论算法、C++实现、邻接矩阵、邻接表、DFS、BFS、Dijkstra算法、Floyd-Warshall算法、Prim算法、最短路径、最小生成树
简介
本文系统阐述了图论基础概念与C++实现方法，涵盖邻接矩阵/邻接表存储结构，深度优先搜索、广度优先搜索、Dijkstra单源最短路径、Floyd-Warshall多源最短路径及Prim最小生成树算法，结合城市交通案例展示完整实现流程，并分析稀疏图优化、并行计算等应用场景。
