C++图论算法实战精解

图论基础理论与实际应用详解（C++实现）

一、基本概念

图 $G$ 由顶点集 $V$ 和边集 $E$ 构成，记为 $G=(V,E)$。

• 有向图：边有方向，$E \subseteq V \times V$
• 无向图：边无方向，$E$ 为无序对集合
• 权重图：边附加权值函数 $w: E \to \mathbb{R}$

存储结构：

1. 邻接矩阵（稠密图适用）：

const int MAXN = 1000;
int graph[MAXN][MAXN]; // 权重存于矩阵

1. 邻接表（稀疏图高效）：

#include <vector>
using namespace std;
struct Edge {
    int to;
    int weight;
};
vector<vector<Edge>> adjList; // adjList[i]存储顶点i的邻接边

二、图的遍历算法

深度优先搜索（DFS）

vector<bool> visited;
void dfs(int u) {
    visited[u] = true;
    for (auto& edge : adjList[u]) {
        if (!visited[edge.to]) {
            dfs(edge.to);
        }
    }
}

应用场景：连通分量检测、拓扑排序、回溯法

广度优先搜索（BFS）

#include <queue>
void bfs(int start) {
    queue<int> q;
    q.push(start);
    visited[start] = true;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (auto& edge : adjList[u]) {
            if (!visited[edge.to]) {
                visited[edge.to] = true;
                q.push(edge.to);
            }
        }
    }
}

应用场景：最短路径（无权图）、层级遍历

三、经典问题与算法

1. 最短路径（Dijkstra算法）

核心思想：贪心策略，适用于非负权图
$$d[v] = \min(d[u] + w(u,v))$$

#include <queue>
#include <climits>
vector<int> dijkstra(int src, int n) {
    vector<int> dist(n, INT_MAX);
    dist[src] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, src});
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d != dist[u]) continue; // 旧数据跳过
        for (auto& edge : adjList[u]) {
            int newDist = d + edge.weight;
            if (newDist < dist[edge.to]) {
                dist[edge.to] = newDist;
                pq.push({newDist, edge.to});
            }
        }
    }
    return dist;
}

2. 拓扑排序（Kahn算法）

适用条件：有向无环图（DAG）
$$ \text{入度} \operatorname{deg}^{-}(v) = 0 \implies \text{可移除} $$

vector<int> topologicalSort(int n) {
    vector<int> indegree(n, 0);
    vector<int> result;
    queue<int> q;
    // 计算入度
    for (int u = 0; u < n; u++)
        for (auto& edge : adjList[u])
            indegree[edge.to]++;
    // 入度为0入队
    for (int i = 0; i < n; i++)
        if (indegree[i] == 0) q.push(i);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        result.push_back(u);
        for (auto& edge : adjList[u]) {
            if (--indegree[edge.to] == 0)
                q.push(edge.to);
        }
    }
    return result.size() == n ? result : vector<int>{}; // 判断环
}

3. 最小生成树（Prim算法）

目标：连接所有顶点的最小权重边集
$$ T \subseteq E, \quad \min \sum_{e \in T} w(e) $$

int prim(int n) {
    vector<bool> visited(n, false);
    vector<int> minDist(n, INT_MAX);
    minDist[0] = 0;
    int total = 0;
    for (int i = 0; i < n; i++) {
        int u = -1;
        for (int j = 0; j < n; j++) // 选最小未访问点
            if (!visited[j] && (u == -1 || minDist[j] < minDist[u]))
                u = j;
        if (minDist[u] == INT_MAX) return -1; // 不连通
        visited[u] = true;
        total += minDist[u];
        for (auto& edge : adjList[u])
            if (edge.weight < minDist[edge.to])
                minDist[edge.to] = edge.weight;
    }
    return total;
}

四、实际应用场景

1. 路径规划

   • 导航系统（Dijkstra/A*算法）
   • 物流配送（带时间窗的最短路径）

2. 依赖分析

   • 编译顺序（拓扑排序）
   • 任务调度（关键路径法）

3. 网络优化

   • 通信网布线（最小生成树）
   • 最大流问题（Ford-Fulkerson算法）

五、复杂问题扩展

• 负权处理：Bellman-Ford算法（动态规划）
• 全源最短路径：Floyd-Warshall算法（三重循环）
• 图的连通性：Tarjan强连通分量算法

提示：实际编码需处理边界条件（如不连通图、自环边），建议使用C++ STL的priority_queue优化Dijkstra，时间复杂度降至 $O(|E|\log|V|)$。