C++信息学奥赛：图论算法教程

图论基本概念

图(Graph)是由顶点(Vertex)和边(Edge)组成的一种数据结构，用于描述事物之间的关系。在信息学中，图是解决复杂问题的重要工具。

基本术语

•
顶点(Vertex)：图中的基本元素，也称为节点(Node)
•
边(Edge)：连接两个顶点的线，表示顶点之间的关系
•
度(Degree)：一个顶点连接的边的数量
•
路径(Path)：从一个顶点到另一个顶点经过的边的序列
•
环(Cycle)：起点和终点相同的路径

图的分类

•
无向图(Undirected Graph)：边没有方向，两个顶点可以互相到达
•
有向图(Directed Graph)：边有方向，只能从一个顶点指向另一个顶点
•
加权图(Weighted Graph)：边上带有权重(值)，表示顶点间关系的强度或代价
•
连通图(Connected Graph)：任意两个顶点之间都存在路径的图
•
树(Tree)：无环的连通图，有n个顶点和n-1条边

无向图

有向图

加权图

图的表示方法

在程序中，图有多种表示方法，选择合适的表示方法对算法效率有很大影响。常用的表示方法有邻接矩阵和邻接表。

1. 邻接矩阵 (Adjacency Matrix)

邻接矩阵是一个二维数组，其中matrix[i][j]表示顶点i和顶点j之间的关系：

对于无权图，matrix[i][j] = 1表示有边，0表示无边
对于加权图，matrix[i][j] = 权重值表示有边，∞表示无边
对于有向图，matrix[i][j]表示从i到j的边

优缺点

优点：

判断两点之间是否有边，时间复杂度O(1)
实现简单直观

缺点：

空间复杂度O(n²)，不适合稀疏图
遍历一个顶点的所有邻接点需要O(n)时间

C++实现代码

// 邻接矩阵表示法
#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 1005;
const int INF = 1e9;

// 无向无权图
int undir_unweighted[MAXN][MAXN];

// 有向加权图
int dir_weighted[MAXN][MAXN];

int main() {
    int n, m; // n:顶点数, m:边数
    cin >> n >> m;
    
    // 初始化无向无权图
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            undir_unweighted[i][j] = 0;
            if (i == j) undir_unweighted[i][j] = 1; // 自环(可选)
        }
    }
    
    // 初始化有向加权图
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            dir_weighted[i][j] = INF;
            if (i == j) dir_weighted[i][j] = 0; // 自身到自身距离为0
        }
    }
    
    // 读入无向无权图的边
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        undir_unweighted[u][v] = 1;
        undir_unweighted[v][u] = 1; // 无向图对称
    }
    
    // 读入有向加权图的边
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        dir_weighted[u][v] = w; // 有向图只需设置一个方向
    }
    
    return 0;
}

2. 邻接表 (Adjacency List)

邻接表是由多个链表（或动态数组）组成的数据结构，每个顶点对应一个链表，存储与该顶点相邻的所有顶点信息：

对于无权图，存储相邻顶点的编号
对于加权图，存储(相邻顶点编号, 权重)的二元组
对于有向图，只存储从当前顶点出发的边

优缺点

优点：

空间复杂度O(n + m)，适合稀疏图
遍历一个顶点的所有邻接点只需要O(k)时间，k为邻接点数量

缺点：

判断两点之间是否有边需要O(k)时间
实现相对复杂

C++实现代码

// 邻接表表示法
#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 1005;

// 无向无权图 - 用vector实现
vector<int> undir_unweighted[MAXN];

// 有向加权图 - 存储pair(顶点, 权重)
vector<pair<int, int>> dir_weighted[MAXN];

int main() {
    int n, m; // n:顶点数, m:边数
    cin >> n >> m;
    
    // 读入无向无权图的边
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        undir_unweighted[u].push_back(v);
        undir_unweighted[v].push_back(u); // 无向图需要添加双向边
    }
    
    // 读入有向加权图的边
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        dir_weighted[u].push_back({v, w}); // 有向图只需添加一个方向
    }
    
    // 遍历顶点u的所有邻接点(示例)
    int u = 1;
    cout << "顶点" << u << "的邻接点: ";
    for (int v : undir_unweighted[u]) {
        cout << v << " ";
    }
    cout << endl;
    
    return 0;
}

选择建议

当顶点数量较少(n ≤ 1000)时，邻接矩阵实现简单，效率也不错
当顶点数量较多(n > 1000)或边比较稀疏时，优先选择邻接表
信息学奥赛中，大多数题目适合用邻接表表示，尤其是当n较大时

图的遍历算法

图的遍历是指从图中的某个顶点出发，按照一定的规则访问图中所有顶点，且每个顶点仅被访问一次。常用的遍历算法有深度优先搜索(DFS)和广度优先搜索(BFS)。

1. 深度优先搜索 (DFS - Depth-First Search)

DFS的基本思想是：

从起始顶点开始访问，并标记为已访问
选择一个未访问的邻接顶点，递归地进行DFS
如果当前顶点的所有邻接顶点都已访问，则回溯到上一个顶点

可以用递归或栈来实现DFS。

复杂度分析

时间复杂度：O(n + m)，其中n是顶点数，m是边数

空间复杂度：O(n)，主要用于存储访问标记和递归栈

C++实现代码 (递归版)

// DFS递归实现
#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 1005;
vector<int> adj[MAXN]; // 邻接表
bool visited[MAXN];    // 标记顶点是否被访问

// 从顶点u开始进行DFS
void dfs(int u) {
    visited[u] = true;  // 标记为已访问
    cout << u << " ";   // 访问顶点u
    
    // 遍历u的所有邻接顶点
    for (int v : adj[u]) {
        if (!visited[v]) {  // 如果未访问过
            dfs(v);         // 递归访问
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    
    // 读入边
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u); // 无向图
    }
    
    // 初始化访问标记
    for (int i = 1; i <= n; i++) {
        visited[i] = false;
    }
    
    // 对所有未访问的顶点进行DFS(处理非连通图)
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            cout << "DFS遍历: ";
            dfs(i);
            cout << endl;
        }
    }
    
    return 0;
}

C++实现代码 (栈版)

// DFS栈实现(非递归)
#include <iostream>
#include <vector>
#include <stack>
using namespace std;

const int MAXN = 1005;
vector<int> adj[MAXN];
bool visited[MAXN];

void dfs_stack(int start) {
    stack<int> s;
    s.push(start);
    visited[start] = true;
    
    cout << "DFS遍历: ";
    
    while (!s.empty()) {
        int u = s.top();
        s.pop();
        cout << u << " ";
        
        // 将邻接顶点入栈(注意顺序会与递归版相反)
        for (auto it = adj[u].rbegin(); it != adj[u].rend(); ++it) {
            int v = *it;
            if (!visited[v]) {
                visited[v] = true;
                s.push(v);
            }
        }
    }
    cout << endl;
}

int main() {
    // 与递归版相同的主函数
    int n, m;
    cin >> n >> m;
    
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    for (int i = 1; i <= n; i++) {
        visited[i] = false;
    }
    
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            dfs_stack(i);
        }
    }
    
    return 0;
}

2. 广度优先搜索 (BFS - Breadth-First Search)

BFS的基本思想是：

从起始顶点开始访问，并标记为已访问
将起始顶点加入队列
当队列非空时，出队一个顶点u，访问u的所有未访问的邻接顶点
将这些邻接顶点标记为已访问并加入队列
重复步骤3-4，直到队列为空

BFS通常用队列来实现，能够按层次顺序访问图中的顶点。

复杂度分析

时间复杂度：O(n + m)，其中n是顶点数，m是边数

空间复杂度：O(n)，主要用于存储访问标记和队列

特别应用

BFS可以用于求解无权图中两点之间的最短路径，因为它按层次访问顶点。

C++实现代码

// BFS实现
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int MAXN = 1005;
vector<int> adj[MAXN]; // 邻接表
bool visited[MAXN];    // 标记顶点是否被访问
int distance[MAXN];    // 存储到起始顶点的距离(用于最短路径)

// 从顶点start开始进行BFS
void bfs(int start) {
    queue<int> q;
    
    // 初始化起始顶点
    visited[start] = true;
    distance[start] = 0;
    q.push(start);
    
    cout << "BFS遍历: ";
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        cout << u << " ";
        
        // 遍历u的所有邻接顶点
        for (int v : adj[u]) {
            if (!visited[v]) {
                visited[v] = true;
                distance[v] = distance[u] + 1; // 距离+1
                q.push(v);
            }
        }
    }
    cout << endl;
}

int main() {
    int n, m;
    cin >> n >> m;
    
    // 读入边
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u); // 无向图
    }
    
    // 初始化
    for (int i = 1; i <= n; i++) {
        visited[i] = false;
        distance[i] = -1; // 表示不可达
    }
    
    // 对所有未访问的顶点进行BFS(处理非连通图)
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            bfs(i);
            
            // 输出距离示例
            cout << "距离起始点" << i << "的距离: ";
            for (int j = 1; j <= n; j++) {
                if (visited[j]) {
                    cout << j << ":" << distance[j] << " ";
                }
            }
            cout << endl << endl;
        }
    }
    
    return 0;
}

最短路径算法

最短路径问题是图论中的经典问题，旨在寻找图中两个顶点之间权重之和最小的路径。根据图的特点和问题需求，有多种算法可供选择。

1. Dijkstra算法

Dijkstra算法用于求解从一个源点到其他所有顶点的最短路径，要求图中所有边的权重都是非负数。

基本思想：

初始化：源点到自身的距离为0，到其他顶点的距离为无穷大
选择距离源点最近且未被处理的顶点u
以u为中介点，更新所有从u可达的顶点v的距离
标记u为已处理
重复步骤2-4，直到所有顶点都被处理

复杂度分析

使用邻接表和优先队列：O(m log n)

使用邻接矩阵：O(n²)

适用场景：单源最短路径，边权非负的图

C++实现代码 (优先队列优化)

// Dijkstra算法(优先队列优化)
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

const int MAXN = 10005;
const int INF = INT_MAX;

// 邻接表: adj[u]存储(u, v, w)的三元组
vector<pair<int, int>> adj[MAXN];
int dist[MAXN]; // 存储到源点的最短距离
bool visited[MAXN]; // 标记顶点是否已处理

// 从源点s出发，计算到所有顶点的最短距离
void dijkstra(int s, int n) {
    // 初始化距离
    for (int i = 1; i <= n; i++) {
        dist[i] = INF;
        visited[i] = false;
    }
    dist[s] = 0;
    
    // 优先队列: (距离, 顶点)，按距离从小到大排序
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, s});
    
    while (!pq.empty()) {
        // 选择距离最近的未处理顶点
        int u = pq.top().second;
        pq.pop();
        
        if (visited[u]) continue;
        visited[u] = true;
        
        // 松弛操作
        for (auto &edge : adj[u]) {
            int v = edge.first;
            int w = edge.second;
            
            // 如果通过u到达v的路径更短，则更新
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
}

int main() {
    int n, m, s;
    cin >> n >> m >> s; // n:顶点数, m:边数, s:源点
    
    // 读入边
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        // 如果是无向图，还需要添加adj[v].push_back({u, w});
    }
    
    // 执行Dijkstra算法
    dijkstra(s, n);
    
    // 输出结果
    for (int i = 1; i <= n; i++) {
        if (dist[i] == INF) {
            cout << "INF ";
        } else {
            cout << dist[i] << " ";
        }
    }
    cout << endl;
    
    return 0;
}

2. Floyd-Warshall算法

Floyd-Warshall算法用于求解图中所有 pairs 顶点之间的最短路径，可以处理带有负权边的图，但不能处理带有负权环的图。

基本思想：动态规划

定义dp[k][i][j]为从i到j，中间顶点只允许使用1..k的最短路径长度
状态转移方程：dp[k][i][j] = min(dp[k-1][i][j], dp[k-1][i][k] + dp[k-1][k][j])
可以优化空间，只用二维数组：dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

复杂度分析

时间复杂度：O(n³)，其中n是顶点数

空间复杂度：O(n²)

适用场景：多源最短路径，顶点数较少(n ≤ 400)的图

C++实现代码

// Floyd-Warshall算法
#include <iostream>
#include <vector>
#include <climits>
using namespace std;

const int MAXN = 405;
const int INF = INT_MAX / 2; // 避免溢出

int dist[MAXN][MAXN]; // dist[i][j]表示i到j的最短距离

// 计算所有顶点对之间的最短路径
void floyd(int n) {
    // k是中间顶点
    for (int k = 1; k <= n; k++) {
        // i是起点
        for (int i = 1; i <= n; i++) {
            // j是终点
            for (int j = 1; j <= n; j++) {
                // 松弛操作：通过k是否能缩短i到j的距离
                if (dist[i][j] > dist[i][k] + dist[k][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m; // n:顶点数, m:边数
    
    // 初始化距离矩阵
    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] = INF;
            }
        }
    }
    
    // 读入边
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        dist[u][v] = min(dist[u][v], w); // 处理重边
        // 如果是无向图，还需要添加dist[v][u] = min(dist[v][u], w);
    }
    
    // 执行Floyd算法
    floyd(n);
    
    // 输出结果
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (dist[i][j] == INF) {
                cout << "INF ";
            } else {
                cout << dist[i][j] << " ";
            }
        }
        cout << endl;
    }
    
    return 0;
}

3. Bellman-Ford算法

Bellman-Ford算法用于求解从一个源点到其他所有顶点的最短路径，可以处理带有负权边的图，并且能够检测图中是否存在负权环。

基本思想：

初始化：源点到自身的距离为0，到其他顶点的距离为无穷大
对所有边进行n-1次松弛操作：对于每条边(u, v)，如果dist[v] > dist[u] + w，则更新dist[v]
第n次松弛操作：如果还能更新距离，则说明图中存在负权环

复杂度分析

时间复杂度：O(nm)，其中n是顶点数，m是边数

空间复杂度：O(n)

适用场景：单源最短路径，存在负权边的图，需要检测负权环

C++实现代码

// Bellman-Ford算法
#include <iostream>
#include <vector>
#include <climits>
using namespace std;

const int MAXN = 1005;
const int MAXM = 10005;
const int INF = INT_MAX;

struct Edge {
    int u, v, w; // 边: u -> v, 权重w
};

Edge edges[MAXM]; // 存储所有边
int dist[MAXN];   // 存储到源点的最短距离
int n, m;         // 顶点数和边数

// 从源点s出发，计算到所有顶点的最短距离
// 返回true表示存在负权环，false表示不存在
bool bellman_ford(int s) {
    // 初始化距离
    for (int i = 1; i <= n; i++) {
        dist[i] = INF;
    }
    dist[s] = 0;
    
    // 进行n-1次松弛操作
    for (int i = 1; i <= n - 1; i++) {
        bool updated = false; // 标记是否有更新
        for (int j = 0; j < m; j++) {
            int u = edges[j].u;
            int v = edges[j].v;
            int w = edges[j].w;
            
            // 如果u可达，且通过u到达v的路径更短
            if (dist[u] != INF && dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                updated = true;
            }
        }
        // 如果没有更新，可以提前退出
        if (!updated) break;
    }
    
    // 检测负权环
    for (int j = 0; j < m; j++) {
        int u = edges[j].u;
        int v = edges[j].v;
        int w = edges[j].w;
        
        if (dist[u] != INF && dist[v] > dist[u] + w) {
            return true; // 存在负权环
        }
    }
    return false; // 不存在负权环
}

int main() {
    int s;
    cin >> n >> m >> s; // n:顶点数, m:边数, s:源点
    
    // 读入边
    for (int i = 0; i < m; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
        // 如果是无向图，还需要添加反向边
        // edges[m+i] = {v, u, w};
    }
    
    // 执行Bellman-Ford算法
    bool has_negative_cycle = bellman_ford(s);
    
    if (has_negative_cycle) {
        cout << "图中存在负权环" << endl;
    } else {
        // 输出结果
        for (int i = 1; i <= n; i++) {
            if (dist[i] == INF) {
                cout << "INF ";
            } else {
                cout << dist[i] << " ";
            }
        }
        cout << endl;
    }
    
    return 0;
}

最小生成树算法

生成树是指包含图中所有顶点且不包含环的子图，边的数量为n-1（n为顶点数）。最小生成树(MST)是指所有生成树中，边的权重之和最小的生成树。

1. Prim算法

Prim算法从一个顶点开始，逐步构建最小生成树：

选择一个起始顶点，将其加入生成树
找出所有一端在生成树中，另一端不在生成树中的边
选择其中权重最小的边，将对应的顶点加入生成树
重复步骤2-3，直到所有顶点都加入生成树

复杂度分析

使用邻接矩阵：O(n²)

使用邻接表和优先队列：O(m log n)

适用场景：稠密图（边数较多）

C++实现代码 (优先队列优化)

// Prim算法(优先队列优化)
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

const int MAXN = 10005;
const int INF = INT_MAX;

// 邻接表: adj[u]存储(u, v, w)
vector<pair<int, int>> adj[MAXN];
bool inMST[MAXN]; // 标记顶点是否已加入MST
int key[MAXN];    // 存储顶点与MST的最小边权

// 计算最小生成树的总权重
int prim(int start, int n) {
    // 初始化
    for (int i = 1; i <= n; i++) {
        key[i] = INF;
        inMST[i] = false;
    }
    key[start] = 0;
    
    // 优先队列: (边权, 顶点)，按边权从小到大排序
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, start});
    
    int total_weight = 0; // MST的总权重
    int count = 0;        // 已加入MST的顶点数
    
    while (!pq.empty() && count < n) {
        int u = pq.top().second;
        int weight = pq.top().first;
        pq.pop();
        
        // 如果顶点已加入MST，跳过
        if (inMST[u]) continue;
        
        // 将顶点加入MST
        inMST[u] = true;
        total_weight += weight;
        count++;
        
        // 更新与u相邻的顶点的key值
        for (auto &edge : adj[u]) {
            int v = edge.first;
            int w = edge.second;
            
            if (!inMST[v] && w < key[v]) {
                key[v] = w;
                pq.push({key[v], v});
            }
        }
    }
    
    // 如果无法生成MST(图不连通)
    if (count != n) return -1;
    return total_weight;
}

int main() {
    int n, m;
    cin >> n >> m; // n:顶点数, m:边数
    
    // 读入边
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w}); // 无向图
    }
    
    // 执行Prim算法，从顶点1开始
    int mst_weight = prim(1, n);
    
    if (mst_weight == -1) {
        cout << "图不连通，无法生成最小生成树" << endl;
    } else {
        cout << "最小生成树的总权重为: " << mst_weight << endl;
    }
    
    return 0;
}

2. Kruskal算法

Kruskal算法按边的权重从小到大排序，逐步选择合适的边构建最小生成树：

将所有边按权重从小到大排序
初始化每个顶点为一个独立的集合
按顺序遍历每条边，如果边的两个顶点属于不同的集合，则将该边加入生成树，并合并两个集合
重复步骤3，直到生成树中包含n-1条边

Kruskal算法需要使用并查集(Union-Find)数据结构来高效地管理和合并集合。

复杂度分析

时间复杂度：O(m log m)，主要花费在边的排序上

空间复杂度：O(n + m)

适用场景：稀疏图（边数较少）

C++实现代码

// Kruskal算法
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 10005;
const int MAXM = 100005;

// 边的结构体
struct Edge {
    int u, v, w;
    // 排序用
    bool operator<(const Edge &other) const {
        return w < other.w;
    }
};

Edge edges[MAXM];
int parent[MAXN]; // 并查集父节点
int rank_[MAXN];  // 并查集秩
int n, m;         // 顶点数和边数

// 并查集初始化
void init() {
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
        rank_[i] = 0;
    }
}

// 查找根节点
int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]); // 路径压缩
    }
    return parent[x];
}

// 合并两个集合
void unite(int x, int y) {
    x = find(x);
    y = find(y);
    
    if (x == y) return;
    
    // 按秩合并
    if (rank_[x] < rank_[y]) {
        parent[x] = y;
    } else {
        parent[y] = x;
        if (rank_[x] == rank_[y]) {
            rank_[x]++;
        }
    }
}

// 计算最小生成树的总权重
int kruskal() {
    sort(edges, edges + m); // 按边权从小到大排序
    init();                 // 初始化并查集
    
    int total_weight = 0; // MST的总权重
    int edge_count = 0;   // 已加入MST的边数
    
    for (int i = 0; i < m; i++) {
        Edge e = edges[i];
        // 如果两个顶点属于不同的集合
        if (find(e.u) != find(e.v)) {
            unite(e.u, e.v);
            total_weight += e.w;
            edge_count++;
            
            // 当加入n-1条边时，生成树已完成
            if (edge_count == n - 1) break;
        }
    }
    
    // 如果无法生成MST(图不连通)
    if (edge_count != n - 1) return -1;
    return total_weight;
}

int main() {
    cin >> n >> m; // n:顶点数, m:边数
    
    // 读入边
    for (int i = 0; i < m; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
    }
    
    // 执行Kruskal算法
    int mst_weight = kruskal();
    
    if (mst_weight == -1) {
        cout << "图不连通，无法生成最小生成树" << endl;
    } else {
        cout << "最小生成树的总权重为: " << mst_weight << endl;
    }
    
    return 0;
}

高级图论算法

1. 拓扑排序 (Topological Sort)

拓扑排序是对有向无环图(DAG)的顶点进行排序，使得对于图中的任意一条有向边(u, v)，顶点u都排在顶点v之前。

基本思想（Kahn算法）：

计算所有顶点的入度
将入度为0的顶点加入队列
当队列非空时，出队一个顶点u，将其加入拓扑序列
对于u的所有邻接顶点v，将v的入度减1，如果v的入度变为0，则将v加入队列
重复步骤3-4，直到队列为空
如果拓扑序列的长度小于顶点数，则图中存在环

应用场景

任务调度问题
课程安排问题
编译依赖关系

C++实现代码

// 拓扑排序(Kahn算法)
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int MAXN = 10005;

vector<int> adj[MAXN]; // 邻接表
int in_degree[MAXN];    // 入度
vector<int> topo_order; // 拓扑序列
int n, m;

// 执行拓扑排序
bool topological_sort() {
    queue<int> q;
    
    // 初始化入度为0的顶点
    for (int i = 1; i <= n; i++) {
        if (in_degree[i] == 0) {
            q.push(i);
        }
    }
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        topo_order.push_back(u);
        
        // 处理u的所有邻接顶点
        for (int v : adj[u]) {
            in_degree[v]--;
            if (in_degree[v] == 0) {
                q.push(v);
            }
        }
    }
    
    // 如果拓扑序列包含所有顶点，则成功
    return topo_order.size() == n;
}

int main() {
    cin >> n >> m;
    
    // 初始化
    for (int i = 1; i <= n; i++) {
        in_degree[i] = 0;
        adj[i].clear();
    }
    
    // 读入边
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        in_degree[v]++;
    }
    
    // 执行拓扑排序
    if (topological_sort()) {
        cout << "拓扑排序结果: ";
        for (int i = 0; i < topo_order.size(); i++) {
            if (i > 0) cout << " ";
            cout << topo_order[i];
        }
        cout << endl;
    } else {
        cout << "图中存在环，无法进行拓扑排序" << endl;
    }
    
    return 0;
}

2. 强连通分量 (SCC - Strongly Connected Components)

在有向图中，强连通分量是指最大的顶点子集，其中任意两个顶点之间都互相可达。

Tarjan算法思想：

使用DFS遍历图，记录每个顶点的发现时间
对于每个顶点u，计算low[u]，表示u或其子孙能回溯到的最早发现时间的顶点
当发现u的某个子顶点v满足low[v] ≥ disc[u]时，说明u是一个强连通分量的根
通过栈来存储当前DFS路径上的顶点，当找到一个强连通分量的根时，弹出栈中所有顶点直到u

应用场景

缩点：将每个强连通分量缩为一个顶点，简化图结构
解决可达性问题
分析有向图的结构特性

C++实现代码 (Tarjan算法)

// Tarjan算法求强连通分量
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

const int MAXN = 10005;
const int INF = 1e9;

vector<int> adj[MAXN]; // 邻接表
int disc[MAXN];         // 发现时间
int low[MAXN];          // 最早可回溯时间
bool in_stack[MAXN];    // 标记是否在栈中
stack<int> stk;        // 存储当前路径上的顶点
vector<vector<int>> sccs; // 存储所有强连通分量
int time_counter;       // 时间计数器
int n, m;

// Tarjan算法核心函数
void tarjan(int u) {
    disc[u] = low[u] = ++time_counter;
    stk.push(u);
    in_stack[u] = true;
    
    // 遍历所有邻接顶点
    for (int v : adj[u]) {
        if (disc[v] == 0) { // 未访问过
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (in_stack[v]) { // 已访问且在当前栈中
            low[u] = min(low[u], disc[v]);
        }
    }
    
    // 找到一个强连通分量的根
    if (low[u] == disc[u]) {
        vector<int> scc;
        // 弹出栈中所有顶点直到u
        while (true) {
            int v = stk.top();
            stk.pop();
            in_stack[v] = false;
            scc.push_back(v);
            
            if (v == u) break;
        }
        sccs.push_back(scc);
    }
}

int main() {
    cin >> n >> m;
    
    // 读入边
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
    }
    
    // 初始化
    time_counter = 0;
    for (int i = 1; i <= n; i++) {
        disc[i] = 0;
        low[i] = 0;
        in_stack[i] = false;
    }
    
    // 对所有未访问的顶点执行Tarjan算法
    for (int i = 1; i <= n; i++) {
        if (disc[i] == 0) {
            tarjan(i);
        }
    }
    
    // 输出结果
    cout << "强连通分量的数量: " << sccs.size() << endl;
    for (int i = 0; i < sccs.size(); i++) {
        cout << "强连通分量 " << i + 1 << ": ";
        for (int v : sccs[i]) {
            cout << v << " ";
        }
        cout << endl;
    }
    
    return 0;
}

图论算法练习题

1

迷宫问题

问题描述：给定一个n×m的迷宫，其中0表示通路，1表示墙壁。从左上角(1,1)出发，到达右下角(n,m)，每次只能上下左右移动。求最短路径的长度。

提示：

可以将迷宫视为一个图，每个单元格是一个顶点，相邻的通路单元格之间有边
使用BFS求解最短路径
需要记录已访问的单元格，避免重复访问

2

城市交通

问题描述：有n个城市和m条公路，每条公路连接两个城市，并有一定的长度。求从城市1到城市n的最短距离。如果无法到达，输出-1。

提示：

使用Dijkstra算法求解单源最短路径
注意处理重边和自环

3

网络布线

问题描述：某地区有n个村庄，现在需要铺设光缆连接所有村庄，每条可能的光缆线路有不同的成本。求连接所有村庄的最小总成本。

提示：

这是一个最小生成树问题
可以使用Prim算法或Kruskal算法实现
注意判断图是否连通

4

课程安排

问题描述：大学有n门课程，有些课程需要先修其他课程（例如，学C++之前需要先学编程基础）。请给出一个合理的课程学习顺序。如果不存在这样的顺序，输出-1。

提示：

这是一个拓扑排序问题
使用Kahn算法实现
如果有环，则不存在合理的学习顺序

5

社交网络

问题描述：在一个社交网络中，有n个用户和m对好友关系（双向）。请找出所有的朋友圈（即强连通分量），并计算每个朋友圈的人数。

提示：

对于无向图，强连通分量就是连通分量
可以使用DFS或BFS遍历找出所有连通分量

图论在信息学奥赛中的重要性

图论基本概念

基本术语

图的分类

无向图

有向图

加权图

图的表示方法

1. 邻接矩阵 (Adjacency Matrix)

优缺点

C++实现代码

2. 邻接表 (Adjacency List)

优缺点

C++实现代码

选择建议

图的遍历算法

1. 深度优先搜索 (DFS - Depth-First Search)

复杂度分析

C++实现代码 (递归版)

C++实现代码 (栈版)

2. 广度优先搜索 (BFS - Breadth-First Search)

复杂度分析

特别应用

C++实现代码

最短路径算法

1. Dijkstra算法

复杂度分析

C++实现代码 (优先队列优化)

2. Floyd-Warshall算法

复杂度分析

C++实现代码

3. Bellman-Ford算法

复杂度分析

C++实现代码

最小生成树算法

1. Prim算法

复杂度分析

C++实现代码 (优先队列优化)

2. Kruskal算法

复杂度分析

C++实现代码

高级图论算法

1. 拓扑排序 (Topological Sort)

应用场景

C++实现代码

2. 强连通分量 (SCC - Strongly Connected Components)

应用场景

C++实现代码 (Tarjan算法)

图论算法练习题

迷宫问题

城市交通

网络布线

课程安排

社交网络