图论算法详解：从DFS/BFS到最短路径

图论在信息学竞赛中的地位

图论是信息学竞赛的重要组成部分，几乎每场比赛都会出现图论题目。掌握图论算法不仅是竞赛的需要，更是培养抽象思维和问题建模能力的重要途径。

图论问题的分类

图的基本概念与存储

图的表示方法对比

三种存储方式的代码实现

邻接矩阵：

const int MAXN = 1005;
int graph[MAXN][MAXN];  // graph[i][j]表示i到j的边权
int n, m;  // n个顶点，m条边

void addEdge(int u, int v, int w) {
    graph[u][v] = w;
    // graph[v][u] = w;  // 无向图需要添加
}

邻接表（vector实现）：

struct Edge {
    int to, weight;
};

vector<Edge> graph[MAXN];

void addEdge(int u, int v, int w) {
    graph[u].push_back({v, w});
    // graph[v].push_back({u, w});  // 无向图
}

链式前向星：

struct Edge {
    int to, next, weight;
} edges[MAXM];

int head[MAXN], edgeCnt = 0;

void addEdge(int u, int v, int w) {
    edges[++edgeCnt] = {v, head[u], w};
    head[u] = edgeCnt;
}

// 遍历u的所有邻居
for (int i = head[u]; i; i = edges[i].next) {
    int v = edges[i].to;
    int w = edges[i].weight;
    // 处理边(u, v)
}

深度优先搜索（DFS）

DFS的核心思想

深度优先搜索像走迷宫，一条路走到底，走不通再回头尝试其他路径。

基础DFS模板

bool visited[MAXN];

void dfs(int u) {
    visited[u] = true;
    
    // 处理节点u
    cout << u << " ";
    
    // 遍历u的所有邻居
    for (int v : graph[u]) {
        if (!visited[v]) {
            dfs(v);
        }
    }
}

DFS的经典应用

1. 判断图的连通性

int countComponents() {
    int components = 0;
    memset(visited, false, sizeof(visited));
    
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            dfs(i);
            components++;
        }
    }
    
    return components;
}

2. 检测环

int color[MAXN];  // 0:白色(未访问) 1:灰色(访问中) 2:黑色(已完成)

bool hasCycle(int u) {
    color[u] = 1;
    
    for (int v : graph[u]) {
        if (color[v] == 1) return true;  // 找到环
        if (color[v] == 0 && hasCycle(v)) return true;
    }
    
    color[u] = 2;
    return false;
}

3. 二分图判定

int color[MAXN];  // 0:未染色 1:红色 2:蓝色

bool isBipartite(int u, int c) {
    color[u] = c;
    
    for (int v : graph[u]) {
        if (color[v] == c) return false;  // 相邻节点同色
        if (color[v] == 0 && !isBipartite(v, 3 - c)) {
            return false;
        }
    }
    
    return true;
}

广度优先搜索（BFS）

BFS的核心思想

广度优先搜索像水波扩散，一层一层向外探索，保证找到的是最短路径。

基础BFS模板

void bfs(int start) {
    queue<int> q;
    bool visited[MAXN] = {false};
    
    q.push(start);
    visited[start] = true;
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        
        // 处理节点u
        cout << u << " ";
        
        for (int v : graph[u]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
}

BFS求最短路径

int bfsShortestPath(int start, int end) {
    queue<int> q;
    int dist[MAXN];
    memset(dist, -1, sizeof(dist));
    
    q.push(start);
    dist[start] = 0;
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        
        if (u == end) return dist[end];
        
        for (int v : graph[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
    
    return -1;  // 无法到达
}

最短路径算法家族

算法选择指南

Dijkstra算法（堆优化版）

struct Edge {
    int to, weight;
};

vector<Edge> graph[MAXN];

vector<int> dijkstra(int start, int n) {
    vector<int> dist(n + 1, INT_MAX);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    
    dist[start] = 0;
    pq.push({0, start});
    
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        
        if (d > dist[u]) continue;
        
        for (auto& edge : graph[u]) {
            int v = edge.to;
            int w = edge.weight;
            
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    
    return dist;
}

Bellman-Ford算法

struct Edge {
    int from, to, weight;
};

vector<Edge> edges;

bool bellmanFord(int start, int n, vector<int>& dist) {
    dist.assign(n + 1, INT_MAX);
    dist[start] = 0;
    
    // 松弛n-1次
    for (int i = 0; i < n - 1; i++) {
        for (auto& e : edges) {
            if (dist[e.from] != INT_MAX) {
                dist[e.to] = min(dist[e.to], dist[e.from] + e.weight);
            }
        }
    }
    
    // 检测负环
    for (auto& e : edges) {
        if (dist[e.from] != INT_MAX && 
            dist[e.from] + e.weight < dist[e.to]) {
            return false;  // 存在负环
        }
    }
    
    return true;
}

SPFA算法（队列优化的Bellman-Ford）

vector<int> spfa(int start, int n) {
    vector<int> dist(n + 1, INT_MAX);
    vector<bool> inQueue(n + 1, false);
    queue<int> q;
    
    dist[start] = 0;
    q.push(start);
    inQueue[start] = true;
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inQueue[u] = false;
        
        for (auto& edge : graph[u]) {
            int v = edge.to;
            int w = edge.weight;
            
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                if (!inQueue[v]) {
                    q.push(v);
                    inQueue[v] = true;
                }
            }
        }
    }
    
    return dist;
}

Floyd算法

void floyd(int n) {
    int dist[MAXN][MAXN];
    
    // 初始化
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) dist[i][j] = 0;
            else dist[i][j] = graph[i][j];  // 邻接矩阵
        }
    }
    
    // 核心算法
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (dist[i][k] != INF && dist[k][j] != INF) {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
}

最小生成树算法

Kruskal算法（并查集）

struct Edge {
    int u, v, weight;
    bool operator<(const Edge& other) const {
        return weight < other.weight;
    }
};

class UnionFind {
    vector<int> parent, rank;
public:
    UnionFind(int n) : parent(n), rank(n, 0) {
        iota(parent.begin(), parent.end(), 0);
    }
    
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    bool unite(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false;
        
        if (rank[px] < rank[py]) swap(px, py);
        parent[py] = px;
        if (rank[px] == rank[py]) rank[px]++;
        
        return true;
    }
};

int kruskal(vector<Edge>& edges, int n) {
    sort(edges.begin(), edges.end());
    UnionFind uf(n + 1);
    
    int mstWeight = 0;
    int edgeCount = 0;
    
    for (auto& e : edges) {
        if (uf.unite(e.u, e.v)) {
            mstWeight += e.weight;
            edgeCount++;
            if (edgeCount == n - 1) break;
        }
    }
    
    return mstWeight;
}

Prim算法（堆优化）

int prim(int start, int n) {
    vector<bool> inMST(n + 1, false);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    
    int mstWeight = 0;
    pq.push({0, start});
    
    while (!pq.empty()) {
        auto [weight, u] = pq.top();
        pq.pop();
        
        if (inMST[u]) continue;
        
        inMST[u] = true;
        mstWeight += weight;
        
        for (auto& edge : graph[u]) {
            if (!inMST[edge.to]) {
                pq.push({edge.weight, edge.to});
            }
        }
    }
    
    return mstWeight;
}

拓扑排序

Kahn算法（BFS实现）

vector<int> topologicalSort(int n) {
    vector<int> inDegree(n + 1, 0);
    
    // 计算入度
    for (int u = 1; u <= n; u++) {
        for (int v : graph[u]) {
            inDegree[v]++;
        }
    }
    
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (inDegree[i] == 0) {
            q.push(i);
        }
    }
    
    vector<int> result;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        result.push_back(u);
        
        for (int v : graph[u]) {
            if (--inDegree[v] == 0) {
                q.push(v);
            }
        }
    }
    
    if (result.size() != n) {
        return {};  // 存在环
    }
    
    return result;
}

高级图论算法

Tarjan算法（强连通分量）

int dfn[MAXN], low[MAXN], timestamp = 0;
stack<int> stk;
bool inStack[MAXN];
int sccCount = 0;

void tarjan(int u) {
    dfn[u] = low[u] = ++timestamp;
    stk.push(u);
    inStack[u] = true;
    
    for (int v : graph[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (inStack[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    
    if (dfn[u] == low[u]) {
        sccCount++;
        while (true) {
            int v = stk.top();
            stk.pop();
            inStack[v] = false;
            // v属于第sccCount个强连通分量
            if (v == u) break;
        }
    }
}

图论题目练习建议

分阶段练习计划

总结

图论是信息学竞赛的基石之一，掌握图论算法需要：

1. 理解本质：每个算法解决什么问题，为什么有效
2. 熟练实现：能够快速准确地写出代码
3. 灵活建模：将实际问题转化为图论模型
4. 优化技巧：根据数据范围选择合适算法
5. 大量练习：见识各种变形题目

记住，图论不仅是算法，更是一种看待问题的方式。通过图的视角，许多复杂问题都能找到优雅的解决方案！