IO竞赛深入解析：图论算法专题完全指南

安全风信子

发布于 2025-11-12 15:33:13

1300

文章被收录于专栏：AI SPPECHAI SPPECH

引言

图论是数学的一个分支，它以图为研究对象，研究顶点和边组成的图形的数学理论和方法。在IO竞赛中，图论问题占据了非常重要的地位，几乎在每一场重要的竞赛中都会出现图论相关的题目。掌握图论算法对于在IO竞赛中取得好成绩至关重要。本文将从图的基本概念出发，深入解析各类图论算法的原理和应用，并通过大量实例帮助读者全面掌握这一重要领域。

图论算法在IO竞赛中的应用领域

路径问题 → 连通性问题 → 匹配问题 → 覆盖问题 → 着色问题 → 网络流问题

算法类型	常见问题	时间复杂度	适用场景
最短路径	单源最短路径、多源最短路径	O(m log n) ~ O(n³)	寻找两点间的最短路径
最小生成树	稠密图、稀疏图	O(m log n) ~ O(m + n log n)	构建最小代价的连通网络
拓扑排序	有向无环图的排序	O(m + n)	任务调度、依赖关系处理
二分图匹配	最大匹配、完美匹配	O(E√V) ~ O(VE)	资源分配、工作安排
网络流	最大流、最小割、最小费用流	O(E²V) ~ O(EV²)	流量优化、资源分配

目录
├── 第一章：图的基本概念与表示方法
├── 第二章：最短路径算法
├── 第三章：最小生成树算法
├── 第四章：图的连通性算法
├── 第五章：拓扑排序与有向无环图
├── 第六章：二分图与匹配算法
├── 第七章：网络流算法
├── 第八章：图论高级算法与技巧
└── 第九章：图论算法实战训练

第一章：图的基本概念与表示方法

1.1 图的基本概念

图是由顶点（Vertex）和边（Edge）组成的一种数据结构，用于表示元素之间的关系。在图论中，我们通常用G=(V,E)来表示一个图，其中V是顶点的集合，E是边的集合。

图的基本术语：

顶点（Vertex）：图中的基本元素，也称为节点（Node）。
边（Edge）：连接两个顶点的线段，表示两个顶点之间的关系。
度数（Degree）：一个顶点所连接的边的数量。在有向图中，分为入度（In-degree）和出度（Out-degree）。
路径（Path）：从一个顶点到另一个顶点的边的序列。
回路（Cycle）：起点和终点相同的路径。
连通性（Connectivity）：在无向图中，如果两个顶点之间存在路径，则称这两个顶点是连通的；在有向图中，如果两个顶点之间存在双向的路径，则称这两个顶点是强连通的。

1.2 图的分类

图可以根据不同的标准进行分类：

无向图（Undirected Graph）：边没有方向的图。
有向图（Directed Graph）：边有方向的图。
加权图（Weighted Graph）：边带有权重的图，也称为网（Network）。
无权图（Unweighted Graph）：边没有权重的图。
简单图（Simple Graph）：没有自环（Loop）和重边（Multiple Edges）的图。
多重图（Multigraph）：允许有重边的图。
完全图（Complete Graph）：任意两个顶点之间都有边相连的图。n个顶点的完全图有n(n-1)/2条边。
树（Tree）：无环的连通图。n个顶点的树有n-1条边。
森林（Forest）：由多棵树组成的图。
有向无环图（DAG）：没有回路的有向图。

1.3 图的表示方法

在计算机中，图通常有以下几种表示方法：

1.3.1 邻接矩阵（Adjacency Matrix）

邻接矩阵是一个n×n的二维数组，其中n是顶点的数量。矩阵的元素A[i][j]表示顶点i和顶点j之间的边的情况。

对于无权图，A[i][j]=1表示顶点i和顶点j之间有一条边，A[i][j]=0表示没有边。
对于加权图，A[i][j]表示顶点i到顶点j的边的权重，如果没有边，则可以用一个特殊值（如无穷大）表示。

邻接矩阵的优点是查询两个顶点之间是否有边的时间复杂度为O(1)，缺点是空间复杂度为O(n²)，对于稀疏图来说会浪费大量空间。

邻接矩阵的C++实现：

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

const int INF = INT_MAX; // 表示无穷大

class Graph {
private:
    int V; // 顶点数
    vector<vector<int>> adjMatrix; // 邻接矩阵
public:
    Graph(int vertices) : V(vertices) {
        adjMatrix.resize(V, vector<int>(V, INF));
        for (int i = 0; i < V; i++) {
            adjMatrix[i][i] = 0; // 自己到自己的距离为0
        }
    }
    
    void addEdge(int u, int v, int weight) {
        adjMatrix[u][v] = weight;
    }
    
    void printAdjMatrix() {
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                if (adjMatrix[i][j] == INF) {
                    cout << "INF ";
                } else {
                    cout << adjMatrix[i][j] << " ";
                }
            }
            cout << endl;
        }
    }
};

int main() {
    Graph g(5);
    g.addEdge(0, 1, 10);
    g.addEdge(0, 2, 3);
    g.addEdge(1, 2, 1);
    g.addEdge(1, 3, 2);
    g.addEdge(2, 1, 4);
    g.addEdge(2, 3, 8);
    g.addEdge(2, 4, 2);
    g.addEdge(3, 4, 7);
    g.addEdge(4, 3, 9);
    
    cout << "邻接矩阵表示：" << endl;
    g.printAdjMatrix();
    
    return 0;
}

1.3.2 邻接表（Adjacency List）

邻接表是一种链式存储结构，它为每个顶点维护一个链表，链表中存储与该顶点相邻的所有顶点及对应的边的权重。

邻接表的优点是空间复杂度为O(V+E)，对于稀疏图来说比较节省空间，缺点是查询两个顶点之间是否有边的时间复杂度为O(V)。

邻接表的C++实现：

#include <iostream>
#include <vector>
using namespace std;

struct Edge {
    int to; // 目标顶点
    int weight; // 边的权重
    Edge(int t, int w) : to(t), weight(w) {}
};

class Graph {
private:
    int V; // 顶点数
    vector<vector<Edge>> adjList; // 邻接表
public:
    Graph(int vertices) : V(vertices) {
        adjList.resize(V);
    }
    
    void addEdge(int u, int v, int weight) {
        adjList[u].emplace_back(v, weight);
    }
    
    void printAdjList() {
        for (int i = 0; i < V; i++) {
            cout << "顶点" << i << "的邻接点：";
            for (const Edge& edge : adjList[i]) {
                cout << "(" << edge.to << ", " << edge.weight << ") ";
            }
            cout << endl;
        }
    }
};

int main() {
    Graph g(5);
    g.addEdge(0, 1, 10);
    g.addEdge(0, 2, 3);
    g.addEdge(1, 2, 1);
    g.addEdge(1, 3, 2);
    g.addEdge(2, 1, 4);
    g.addEdge(2, 3, 8);
    g.addEdge(2, 4, 2);
    g.addEdge(3, 4, 7);
    g.addEdge(4, 3, 9);
    
    cout << "邻接表表示：" << endl;
    g.printAdjList();
    
    return 0;
}

1.3.3 边列表（Edge List）

边列表是一种简单的图表示方法，它使用一个列表来存储图中的所有边。每条边通常表示为一个三元组（u, v, w），其中u和v是边的两个顶点，w是边的权重（对于无权图，可以省略w）。

边列表的优点是简单直观，缺点是查询两个顶点之间是否有边的时间复杂度为O(E)，不适合频繁查询边的情况。

边列表的C++实现：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Edge {
    int from; // 起始顶点
    int to; // 目标顶点
    int weight; // 边的权重
    Edge(int f, int t, int w) : from(f), to(t), weight(w) {}
    
    // 用于排序
    bool operator<(const Edge& other) const {
        return weight < other.weight;
    }
};

class Graph {
private:
    int V; // 顶点数
    vector<Edge> edges; // 边列表
public:
    Graph(int vertices) : V(vertices) {}
    
    void addEdge(int u, int v, int weight) {
        edges.emplace_back(u, v, weight);
    }
    
    void printEdges() {
        for (const Edge& edge : edges) {
            cout << edge.from << " -> " << edge.to << " (" << edge.weight << ")" << endl;
        }
    }
};

int main() {
    Graph g(5);
    g.addEdge(0, 1, 10);
    g.addEdge(0, 2, 3);
    g.addEdge(1, 2, 1);
    g.addEdge(1, 3, 2);
    g.addEdge(2, 1, 4);
    g.addEdge(2, 3, 8);
    g.addEdge(2, 4, 2);
    g.addEdge(3, 4, 7);
    g.addEdge(4, 3, 9);
    
    cout << "边列表表示：" << endl;
    g.printEdges();
    
    return 0;
}

1.4 图的遍历算法

图的遍历是指从图中的某个顶点出发，按照某种顺序访问图中的所有顶点，且每个顶点只被访问一次。图的遍历算法主要有两种：深度优先搜索（DFS）和广度优先搜索（BFS）。

1.4.1 深度优先搜索（DFS）

深度优先搜索是一种递归的遍历算法，它从一个顶点出发，尽可能深地搜索图的分支，直到无法继续前进时，才回溯到上一个顶点，继续搜索其他分支。

DFS的基本步骤：

选择一个起始顶点，将其标记为已访问。
对于起始顶点的每个未访问过的邻接顶点，递归地执行DFS。
当所有邻接顶点都被访问过之后，回溯到上一个顶点。

DFS的C++实现：

#include <iostream>
#include <vector>
using namespace std;

void dfs(int u, const vector<vector<int>>& adj, vector<bool>& visited) {
    visited[u] = true;
    cout << u << " ";
    
    for (int v : adj[u]) {
        if (!visited[v]) {
            dfs(v, adj, visited);
        }
    }
}

int main() {
    int V = 5;
    vector<vector<int>> adj(V);
    
    // 构建邻接表
    adj[0].push_back(1);
    adj[0].push_back(2);
    adj[1].push_back(0);
    adj[1].push_back(2);
    adj[1].push_back(3);
    adj[2].push_back(0);
    adj[2].push_back(1);
    adj[2].push_back(3);
    adj[2].push_back(4);
    adj[3].push_back(1);
    adj[3].push_back(2);
    adj[3].push_back(4);
    adj[4].push_back(2);
    adj[4].push_back(3);
    
    vector<bool> visited(V, false);
    cout << "DFS遍历结果：";
    dfs(0, adj, visited);
    cout << endl;
    
    return 0;
}

1.4.2 广度优先搜索（BFS）

广度优先搜索是一种层次遍历算法，它从一个顶点出发，先访问该顶点的所有邻接顶点，然后再依次访问这些邻接顶点的邻接顶点，直到访问完图中的所有顶点。

BFS的基本步骤：

选择一个起始顶点，将其加入队列，并标记为已访问。
当队列不为空时，从队列中取出一个顶点，访问它的所有未访问过的邻接顶点，将这些顶点加入队列，并标记为已访问。
重复步骤2，直到队列为空。

BFS的C++实现：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

void bfs(int start, const vector<vector<int>>& adj, vector<bool>& visited) {
    queue<int> q;
    q.push(start);
    visited[start] = true;
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        cout << u << " ";
        
        for (int v : adj[u]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
}

int main() {
    int V = 5;
    vector<vector<int>> adj(V);
    
    // 构建邻接表
    adj[0].push_back(1);
    adj[0].push_back(2);
    adj[1].push_back(0);
    adj[1].push_back(2);
    adj[1].push_back(3);
    adj[2].push_back(0);
    adj[2].push_back(1);
    adj[2].push_back(3);
    adj[2].push_back(4);
    adj[3].push_back(1);
    adj[3].push_back(2);
    adj[3].push_back(4);
    adj[4].push_back(2);
    adj[4].push_back(3);
    
    vector<bool> visited(V, false);
    cout << "BFS遍历结果：";
    bfs(0, adj, visited);
    cout << endl;
    
    return 0;
}

第二章：最短路径算法

2.1 最短路径问题概述

最短路径问题是图论中的经典问题，它要求在加权图中找到从一个顶点到另一个顶点的路径，使得路径上的边的权重之和最小。最短路径问题可以分为以下几种类型：

单源最短路径（Single-Source Shortest Paths）：从一个顶点出发，到其他所有顶点的最短路径。
单目标最短路径（Single-Destination Shortest Paths）：从其他所有顶点出发，到一个顶点的最短路径。
单对顶点最短路径（Single-Pair Shortest Paths）：从一个顶点出发，到另一个特定顶点的最短路径。
多源最短路径（All-Pairs Shortest Paths）：计算图中所有顶点对之间的最短路径。

2.2 单源最短路径算法

2.2.1 Dijkstra算法

Dijkstra算法是一种用于解决单源最短路径问题的贪心算法，它要求图中的边的权重都是非负的。Dijkstra算法的基本思想是每次从未访问的顶点中选择距离最小的顶点，然后更新其邻接顶点的距离。

Dijkstra算法的基本步骤：

初始化距离数组，将起始顶点的距离设为0，其他顶点的距离设为无穷大。
维护一个优先队列，用于存储未访问的顶点及其当前的距离。
每次从优先队列中取出距离最小的顶点，标记为已访问。
对于该顶点的每个未访问的邻接顶点，更新其距离，如果发现更短的路径，则将该邻接顶点加入优先队列。
重复步骤3和4，直到优先队列为空。

Dijkstra算法的C++实现：

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

struct Edge {
    int to;
    int weight;
    Edge(int t, int w) : to(t), weight(w) {}
};

vector<int> dijkstra(int start, const vector<vector<Edge>>& graph) {
    int n = graph.size();
    vector<int> dist(n, INT_MAX);
    vector<bool> visited(n, false);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    
    dist[start] = 0;
    pq.push({0, start});
    
    while (!pq.empty()) {
        int u = pq.top().second;
        int d = pq.top().first;
        pq.pop();
        
        if (visited[u]) continue;
        visited[u] = true;
        
        for (const Edge& edge : graph[u]) {
            int v = edge.to;
            int weight = edge.weight;
            if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }
    
    return dist;
}

int main() {
    int V = 5;
    vector<vector<Edge>> graph(V);
    
    // 构建图
    graph[0].emplace_back(1, 10);
    graph[0].emplace_back(2, 3);
    graph[1].emplace_back(2, 1);
    graph[1].emplace_back(3, 2);
    graph[2].emplace_back(1, 4);
    graph[2].emplace_back(3, 8);
    graph[2].emplace_back(4, 2);
    graph[3].emplace_back(4, 7);
    graph[4].emplace_back(3, 9);
    
    vector<int> dist = dijkstra(0, graph);
    
    cout << "从顶点0到各顶点的最短距离：" << endl;
    for (int i = 0; i < V; i++) {
        if (dist[i] == INT_MAX) {
            cout << "顶点" << i << ": 不可达" << endl;
        } else {
            cout << "顶点" << i << ": " << dist[i] << endl;
        }
    }
    
    return 0;
}

2.2.2 Bellman-Ford算法

Bellman-Ford算法是一种用于解决单源最短路径问题的动态规划算法，它可以处理含有负权边的图，但不能处理含有负权回路的图。Bellman-Ford算法的基本思想是通过松弛操作逐步逼近最短路径。

Bellman-Ford算法的基本步骤：

初始化距离数组，将起始顶点的距离设为0，其他顶点的距离设为无穷大。
对图中的所有边进行V-1次松弛操作，其中V是顶点的数量。
检查是否存在负权回路，如果存在，则无法求出最短路径。

Bellman-Ford算法的C++实现：

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

struct Edge {
    int from;
    int to;
    int weight;
    Edge(int f, int t, int w) : from(f), to(t), weight(w) {}
};

vector<int> bellmanFord(int start, int V, const vector<Edge>& edges) {
    vector<int> dist(V, INT_MAX);
    dist[start] = 0;
    
    // 进行V-1次松弛操作
    for (int i = 0; i < V - 1; i++) {
        for (const Edge& edge : edges) {
            int u = edge.from;
            int v = edge.to;
            int weight = edge.weight;
            if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
            }
        }
    }
    
    // 检查是否存在负权回路
    for (const Edge& edge : edges) {
        int u = edge.from;
        int v = edge.to;
        int weight = edge.weight;
        if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
            cout << "图中存在负权回路" << endl;
            return {};
        }
    }
    
    return dist;
}

int main() {
    int V = 5;
    vector<Edge> edges;
    
    // 构建图
    edges.emplace_back(0, 1, -1);
    edges.emplace_back(0, 2, 4);
    edges.emplace_back(1, 2, 3);
    edges.emplace_back(1, 3, 2);
    edges.emplace_back(1, 4, 2);
    edges.emplace_back(3, 2, 5);
    edges.emplace_back(3, 1, 1);
    edges.emplace_back(4, 3, -3);
    
    vector<int> dist = bellmanFord(0, V, edges);
    
    if (!dist.empty()) {
        cout << "从顶点0到各顶点的最短距离：" << endl;
        for (int i = 0; i < V; i++) {
            if (dist[i] == INT_MAX) {
                cout << "顶点" << i << ": 不可达" << endl;
            } else {
                cout << "顶点" << i << ": " << dist[i] << endl;
            }
        }
    }
    
    return 0;
}

2.2.3 SPFA算法

SPFA（Shortest Path Faster Algorithm）算法是Bellman-Ford算法的一种优化版本，它利用队列来减少不必要的松弛操作，提高了算法的效率。SPFA算法特别适合处理含有负权边但没有负权回路的图。

SPFA算法的基本步骤：

初始化距离数组，将起始顶点的距离设为0，其他顶点的距离设为无穷大。
将起始顶点加入队列。
当队列不为空时，取出队首顶点，对其所有邻接顶点进行松弛操作，如果发现更短的路径，则更新距离，并将该邻接顶点加入队列（如果不在队列中）。
重复步骤3，直到队列为空。
可以通过记录每个顶点的入队次数来检测是否存在负权回路。

SPFA算法的C++实现：

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

struct Edge {
    int to;
    int weight;
    Edge(int t, int w) : to(t), weight(w) {}
};

vector<int> spfa(int start, const vector<vector<Edge>>& graph) {
    int n = graph.size();
    vector<int> dist(n, INT_MAX);
    vector<bool> inQueue(n, false);
    vector<int> inCount(n, 0); // 记录每个顶点的入队次数
    queue<int> q;
    
    dist[start] = 0;
    q.push(start);
    inQueue[start] = true;
    inCount[start]++;
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inQueue[u] = false;
        
        for (const Edge& edge : graph[u]) {
            int v = edge.to;
            int weight = edge.weight;
            if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                if (!inQueue[v]) {
                    q.push(v);
                    inQueue[v] = true;
                    inCount[v]++;
                    // 如果入队次数超过n，说明存在负权回路
                    if (inCount[v] > n) {
                        cout << "图中存在负权回路" << endl;
                        return {};
                    }
                }
            }
        }
    }
    
    return dist;
}

int main() {
    int V = 5;
    vector<vector<Edge>> graph(V);
    
    // 构建图
    graph[0].emplace_back(1, -1);
    graph[0].emplace_back(2, 4);
    graph[1].emplace_back(2, 3);
    graph[1].emplace_back(3, 2);
    graph[1].emplace_back(4, 2);
    graph[3].emplace_back(2, 5);
    graph[3].emplace_back(1, 1);
    graph[4].emplace_back(3, -3);
    
    vector<int> dist = spfa(0, graph);
    
    if (!dist.empty()) {
        cout << "从顶点0到各顶点的最短距离：" << endl;
        for (int i = 0; i < V; i++) {
            if (dist[i] == INT_MAX) {
                cout << "顶点" << i << ": 不可达" << endl;
            } else {
                cout << "顶点" << i << ": " << dist[i] << endl;
            }
        }
    }
    
    return 0;
}

2.3 多源最短路径算法

2.3.1 Floyd-Warshall算法

Floyd-Warshall算法是一种用于解决多源最短路径问题的动态规划算法，它可以处理含有负权边的图，但不能处理含有负权回路的图。Floyd-Warshall算法的基本思想是通过三重循环，逐步更新任意两个顶点之间的最短路径。

Floyd-Warshall算法的基本步骤：

初始化距离矩阵，使用邻接矩阵表示图。
对于每个顶点k，作为中间顶点，更新任意两个顶点i和j之间的最短路径。
三重循环结束后，距离矩阵中存储的就是任意两个顶点之间的最短路径长度。

Floyd-Warshall算法的C++实现：

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

const int INF = INT_MAX;

vector<vector<int>> floydWarshall(vector<vector<int>>& graph) {
    int n = graph.size();
    vector<vector<int>> dist = graph;
    
    // 对每个顶点k作为中间顶点
    for (int k = 0; k < n; k++) {
        // 更新任意两个顶点i和j之间的最短路径
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
    
    // 检查是否存在负权回路
    for (int i = 0; i < n; i++) {
        if (dist[i][i] < 0) {
            cout << "图中存在负权回路" << endl;
            return {};
        }
    }
    
    return dist;
}

int main() {
    int V = 4;
    vector<vector<int>> graph = {
        {0, 3, INF, 7},
        {8, 0, 2, INF},
        {5, INF, 0, 1},
        {2, INF, INF, 0}
    };
    
    vector<vector<int>> dist = floydWarshall(graph);
    
    if (!dist.empty()) {
        cout << "任意两个顶点之间的最短距离：" << endl;
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                if (dist[i][j] == INF) {
                    cout << "INF ";
                } else {
                    cout << dist[i][j] << " ";
                }
            }
            cout << endl;
        }
    }
    
    return 0;
}

2.4 最短路径算法的应用场景

算法	适用场景	优点	缺点
Dijkstra	非负权边的图，求单源最短路径	时间复杂度低，效率高	不能处理负权边
Bellman-Ford	含有负权边的图，求单源最短路径	可以处理负权边，可以检测负权回路	时间复杂度高
SPFA	含有负权边的图，求单源最短路径	效率高于Bellman-Ford，实用性强	在最坏情况下时间复杂度仍较高
Floyd-Warshall	任意权边的图（不含负权回路），求多源最短路径	实现简单，代码简洁	时间复杂度高，仅适用于小规模图

第三章：最小生成树算法

3.1 最小生成树问题概述

最小生成树（Minimum Spanning Tree，MST）是指在一个加权的无向图中，找到一棵生成树，使得生成树中所有边的权重之和最小。最小生成树问题在网络设计、电路设计、交通规划等领域有着广泛的应用。

生成树的定义：一个连通图的生成树是一个包含图中所有顶点的树，即生成树是图的一个子图，它是连通的，并且没有回路，同时包含图中所有的顶点。

最小生成树的性质：

唯一性：如果图中的所有边的权重都不相同，那么最小生成树是唯一的。
边数：n个顶点的最小生成树有n-1条边。
割性质：对于任意一个割，割中的最小权边一定在某个最小生成树中。
回路性质：对于任意一个回路，回路中的最大权边一定不在某个最小生成树中。

3.2 Kruskal算法

Kruskal算法是一种基于贪心策略的最小生成树算法，它的基本思想是按照边的权重从小到大的顺序选择边，每次选择一条不构成回路的边，直到选择了n-1条边为止。

Kruskal算法的基本步骤：

将图中的所有边按照权重从小到大排序。
初始化一个并查集，每个顶点各自构成一个集合。
依次考察排序后的每条边，如果这条边的两个顶点属于不同的集合，则将这条边加入最小生成树，并将这两个顶点所在的集合合并。
重复步骤3，直到最小生成树中包含了n-1条边。

Kruskal算法的C++实现：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Edge {
    int from;
    int to;
    int weight;
    Edge(int f, int t, int w) : from(f), to(t), weight(w) {}
    
    bool operator<(const Edge& other) const {
        return weight < other.weight;
    }
};

struct UnionFind {
    vector<int> parent;
    vector<int> rank;
    
    UnionFind(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }
    
    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]++;
            }
        }
    }
};

vector<Edge> kruskal(int V, vector<Edge>& edges) {
    sort(edges.begin(), edges.end());
    UnionFind uf(V);
    vector<Edge> mst;
    
    for (const Edge& edge : edges) {
        if (uf.find(edge.from) != uf.find(edge.to)) {
            uf.unite(edge.from, edge.to);
            mst.push_back(edge);
            if (mst.size() == V - 1) {
                break;
            }
        }
    }
    
    return mst;
}

int main() {
    int V = 4;
    vector<Edge> edges;
    
    // 构建图
    edges.emplace_back(0, 1, 10);
    edges.emplace_back(0, 2, 6);
    edges.emplace_back(0, 3, 5);
    edges.emplace_back(1, 3, 15);
    edges.emplace_back(2, 3, 4);
    
    vector<Edge> mst = kruskal(V, edges);
    
    cout << "最小生成树的边：" << endl;
    int totalWeight = 0;
    for (const Edge& edge : mst) {
        cout << edge.from << " -- " << edge.to << " (" << edge.weight << ")" << endl;
        totalWeight += edge.weight;
    }
    cout << "最小生成树的总权重：" << totalWeight << endl;
    
    return 0;
}

3.3 Prim算法

Prim算法也是一种基于贪心策略的最小生成树算法，它的基本思想是从一个顶点开始，每次选择一条连接生成树和非生成树顶点的最小权边，直到生成树包含所有顶点。

Prim算法的基本步骤：

选择一个起始顶点，将其加入生成树。
维护一个数组，记录每个非生成树顶点到生成树的最小距离。
每次选择距离生成树最近的非生成树顶点，将其加入生成树，并更新其他非生成树顶点到生成树的最小距离。
重复步骤3，直到生成树包含所有顶点。

Prim算法的C++实现（使用优先队列优化）：

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

struct Edge {
    int to;
    int weight;
    Edge(int t, int w) : to(t), weight(w) {}
};

vector<pair<int, int>> prim(int V, const vector<vector<Edge>>& graph) {
    vector<int> minDist(V, INT_MAX); // 记录每个顶点到生成树的最小距离
    vector<int> parent(V, -1); // 记录生成树中每个顶点的父节点
    vector<bool> inMST(V, false); // 记录顶点是否在生成树中
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    
    int start = 0;
    minDist[start] = 0;
    pq.push({0, start});
    
    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        
        if (inMST[u]) continue;
        inMST[u] = true;
        
        for (const Edge& edge : graph[u]) {
            int v = edge.to;
            int weight = edge.weight;
            if (!inMST[v] && weight < minDist[v]) {
                minDist[v] = weight;
                parent[v] = u;
                pq.push({minDist[v], v});
            }
        }
    }
    
    // 构建最小生成树的边
    vector<pair<int, int>> mstEdges;
    for (int i = 1; i < V; i++) {
        if (parent[i] != -1) {
            mstEdges.push_back({parent[i], i});
        }
    }
    
    return mstEdges;
}

int main() {
    int V = 4;
    vector<vector<Edge>> graph(V);
    
    // 构建图
    graph[0].emplace_back(1, 10);
    graph[0].emplace_back(2, 6);
    graph[0].emplace_back(3, 5);
    graph[1].emplace_back(0, 10);
    graph[1].emplace_back(3, 15);
    graph[2].emplace_back(0, 6);
    graph[2].emplace_back(3, 4);
    graph[3].emplace_back(0, 5);
    graph[3].emplace_back(1, 15);
    graph[3].emplace_back(2, 4);
    
    vector<pair<int, int>> mstEdges = prim(V, graph);
    
    cout << "最小生成树的边：" << endl;
    for (const auto& edge : mstEdges) {
        cout << edge.first << " -- " << edge.second << endl;
    }
    
    return 0;
}

3.4 两种算法的比较

算法	时间复杂度	空间复杂度	适用场景	优势
Kruskal	O(E log E)	O(E + V)	稀疏图	实现简单，适合边数少的图
Prim	O(E log V)	O(E + V)	稠密图	对于顶点数少的图效率更高

第四章：图的连通性算法

4.1 连通性问题概述

连通性是图论中的一个基本概念，它描述了图中顶点之间的可达性。在无向图中，如果两个顶点之间存在路径，则称这两个顶点是连通的；在有向图中，如果两个顶点之间存在双向的路径，则称这两个顶点是强连通的。

连通性问题主要包括以下几种类型：

无向图的连通性：判断无向图是否连通，或者将无向图分解为连通分量。
有向图的强连通性：判断有向图是否强连通，或者将有向图分解为强连通分量。
双连通性：判断图是否双连通（没有割点或桥），或者将图分解为双连通分量。

4.2 无向图的连通分量

无向图的连通分量是指最大的顶点子集，其中任意两个顶点之间都存在路径。计算无向图的连通分量可以使用DFS或BFS算法。

使用DFS计算无向图的连通分量的C++实现：

#include <iostream>
#include <vector>
using namespace std;

void dfs(int u, const vector<vector<int>>& adj, vector<bool>& visited, vector<int>& component, int label) {
    visited[u] = true;
    component[u] = label;
    
    for (int v : adj[u]) {
        if (!visited[v]) {
            dfs(v, adj, visited, component, label);
        }
    }
}

vector<int> findComponents(int V, const vector<vector<int>>& adj) {
    vector<bool> visited(V, false);
    vector<int> component(V, -1);
    int label = 0;
    
    for (int i = 0; i < V; i++) {
        if (!visited[i]) {
            dfs(i, adj, visited, component, label);
            label++;
        }
    }
    
    return component;
}

int main() {
    int V = 8;
    vector<vector<int>> adj(V);
    
    // 构建图
    adj[0].push_back(1);
    adj[1].push_back(0);
    adj[1].push_back(2);
    adj[2].push_back(1);
    adj[3].push_back(4);
    adj[4].push_back(3);
    adj[5].push_back(6);
    adj[5].push_back(7);
    adj[6].push_back(5);
    adj[7].push_back(5);
    
    vector<int> component = findComponents(V, adj);
    
    cout << "每个顶点所属的连通分量：" << endl;
    for (int i = 0; i < V; i++) {
        cout << "顶点" << i << "：连通分量" << component[i] << endl;
    }
    
    return 0;
}

4.3 有向图的强连通分量

有向图的强连通分量是指最大的顶点子集，其中任意两个顶点之间都存在双向的路径。计算有向图的强连通分量的常用算法有Kosaraju算法、Tarjan算法和Gabow算法。

4.3.1 Kosaraju算法

Kosaraju算法是一种基于两次DFS的强连通分量算法，它的基本思想是：

第一次DFS：对原图进行DFS，记录顶点的完成顺序（后序遍历顺序）。
第二次DFS：按照第一次DFS的完成顺序的逆序，对转置图（所有边的方向都反转）进行DFS，每次DFS访问的顶点集合就是一个强连通分量。

Kosaraju算法的C++实现：

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;

void dfs1(int u, const vector<vector<int>>& adj, vector<bool>& visited, stack<int>& finishOrder) {
    visited[u] = true;
    
    for (int v : adj[u]) {
        if (!visited[v]) {
            dfs1(v, adj, visited, finishOrder);
        }
    }
    
    finishOrder.push(u);
}

void dfs2(int u, const vector<vector<int>>& transposedAdj, vector<bool>& visited, vector<int>& component, int label) {
    visited[u] = true;
    component[u] = label;
    
    for (int v : transposedAdj[u]) {
        if (!visited[v]) {
            dfs2(v, transposedAdj, visited, component, label);
        }
    }
}

vector<int> kosaraju(int V, const vector<vector<int>>& adj) {
    vector<bool> visited(V, false);
    stack<int> finishOrder;
    
    // 第一次DFS，记录完成顺序
    for (int i = 0; i < V; i++) {
        if (!visited[i]) {
            dfs1(i, adj, visited, finishOrder);
        }
    }
    
    // 构建转置图
    vector<vector<int>> transposedAdj(V);
    for (int u = 0; u < V; u++) {
        for (int v : adj[u]) {
            transposedAdj[v].push_back(u);
        }
    }
    
    // 第二次DFS，按照完成顺序的逆序访问转置图
    fill(visited.begin(), visited.end(), false);
    vector<int> component(V, -1);
    int label = 0;
    
    while (!finishOrder.empty()) {
        int u = finishOrder.top();
        finishOrder.pop();
        
        if (!visited[u]) {
            dfs2(u, transposedAdj, visited, component, label);
            label++;
        }
    }
    
    return component;
}

int main() {
    int V = 5;
    vector<vector<int>> adj(V);
    
    // 构建图
    adj[0].push_back(1);
    adj[1].push_back(2);
    adj[2].push_back(0);
    adj[2].push_back(3);
    adj[3].push_back(4);
    adj[4].push_back(3);
    
    vector<int> component = kosaraju(V, adj);
    
    cout << "每个顶点所属的强连通分量：" << endl;
    for (int i = 0; i < V; i++) {
        cout << "顶点" << i << "：强连通分量" << component[i] << endl;
    }
    
    return 0;
}

4.3.2 Tarjan算法

Tarjan算法是一种基于一次DFS的强连通分量算法，它的基本思想是使用两个数组dfn和low来记录顶点的发现时间和能够回溯到的最早的顶点的发现时间。如果一个顶点的dfn值等于其low值，则该顶点是一个强连通分量的根。

Tarjan算法的C++实现：

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

void tarjan(int u, const vector<vector<int>>& adj, vector<int>& dfn, vector<int>& low, vector<bool>& inStack, stack<int>& s, vector<vector<int>>& components, int& time) {
    dfn[u] = low[u] = ++time;
    s.push(u);
    inStack[u] = true;
    
    for (int v : adj[u]) {
        if (!dfn[v]) { // 未访问过
            tarjan(v, adj, dfn, low, inStack, s, components, time);
            low[u] = min(low[u], low[v]);
        } else if (inStack[v]) { // 在栈中，说明是回边
            low[u] = min(low[u], dfn[v]);
        }
    }
    
    if (dfn[u] == low[u]) { // 找到一个强连通分量的根
        vector<int> component;
        while (true) {
            int v = s.top();
            s.pop();
            inStack[v] = false;
            component.push_back(v);
            if (v == u) break;
        }
        components.push_back(component);
    }
}

vector<vector<int>> findSCC(int V, const vector<vector<int>>& adj) {
    vector<int> dfn(V, 0);
    vector<int> low(V, 0);
    vector<bool> inStack(V, false);
    stack<int> s;
    vector<vector<int>> components;
    int time = 0;
    
    for (int i = 0; i < V; i++) {
        if (!dfn[i]) {
            tarjan(i, adj, dfn, low, inStack, s, components, time);
        }
    }
    
    return components;
}

int main() {
    int V = 5;
    vector<vector<int>> adj(V);
    
    // 构建图
    adj[0].push_back(1);
    adj[1].push_back(2);
    adj[2].push_back(0);
    adj[2].push_back(3);
    adj[3].push_back(4);
    adj[4].push_back(3);
    
    vector<vector<int>> components = findSCC(V, adj);
    
    cout << "强连通分量：" << endl;
    for (int i = 0; i < components.size(); i++) {
        cout << "强连通分量" << i << ": ";
        for (int v : components[i]) {
            cout << v << " ";
        }
        cout << endl;
    }
    
    return 0;
}

4.4 割点和桥

割点（Articulation Point）是指无向图中，删除该顶点及其相关的边后，图的连通分量数量增加的顶点。桥（Bridge）是指无向图中，删除该边后，图的连通分量数量增加的边。

4.4.1 寻找割点

寻找割点的常用算法是Tarjan算法的一个变种，它的基本思想是使用dfn和low两个数组来记录顶点的发现时间和能够回溯到的最早的顶点的发现时间。对于根顶点，如果有两个或更多的子树，则根顶点是割点；对于非根顶点，如果存在一个子节点，其low值大于等于当前顶点的dfn值，则当前顶点是割点。

寻找割点的C++实现：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void findArticulationPoints(int u, int parent, const vector<vector<int>>& adj, vector<int>& dfn, vector<int>& low, vector<bool>& isArticulation, int& time) {
    dfn[u] = low[u] = ++time;
    int children = 0;
    
    for (int v : adj[u]) {
        if (v == parent) continue;
        
        if (!dfn[v]) { // 未访问过
            children++;
            findArticulationPoints(v, u, adj, dfn, low, isArticulation, time);
            low[u] = min(low[u], low[v]);
            
            // 根顶点的情况
            if (parent == -1 && children > 1) {
                isArticulation[u] = true;
            }
            
            // 非根顶点的情况
            if (parent != -1 && low[v] >= dfn[u]) {
                isArticulation[u] = true;
            }
        } else { // 已访问过，更新low值
            low[u] = min(low[u], dfn[v]);
        }
    }
}

vector<int> getArticulationPoints(int V, const vector<vector<int>>& adj) {
    vector<int> dfn(V, 0);
    vector<int> low(V, 0);
    vector<bool> isArticulation(V, false);
    int time = 0;
    
    for (int i = 0; i < V; i++) {
        if (!dfn[i]) {
            findArticulationPoints(i, -1, adj, dfn, low, isArticulation, time);
        }
    }
    
    vector<int> articulationPoints;
    for (int i = 0; i < V; i++) {
        if (isArticulation[i]) {
            articulationPoints.push_back(i);
        }
    }
    
    return articulationPoints;
}

int main() {
    int V = 5;
    vector<vector<int>> adj(V);
    
    // 构建图
    adj[0].push_back(1);
    adj[1].push_back(0);
    adj[1].push_back(2);
    adj[2].push_back(1);
    adj[2].push_back(3);
    adj[3].push_back(2);
    adj[3].push_back(4);
    adj[4].push_back(3);
    
    vector<int> articulationPoints = getArticulationPoints(V, adj);
    
    cout << "割点：";
    for (int u : articulationPoints) {
        cout << u << " ";
    }
    cout << endl;
    
    return 0;
}

4.4.2 寻找桥

寻找桥的算法也是Tarjan算法的一个变种，它的基本思想是对于一条边(u, v)，如果low[v] > dfn[u]，则这条边是桥。

寻找桥的C++实现：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void findBridges(int u, int parent, const vector<vector<int>>& adj, vector<int>& dfn, vector<int>& low, vector<pair<int, int>>& bridges, int& time) {
    dfn[u] = low[u] = ++time;
    
    for (int v : adj[u]) {
        if (v == parent) continue;
        
        if (!dfn[v]) { // 未访问过
            findBridges(v, u, adj, dfn, low, bridges, time);
            low[u] = min(low[u], low[v]);
            
            // 检查是否是桥
            if (low[v] > dfn[u]) {
                bridges.push_back({u, v});
            }
        } else { // 已访问过，更新low值
            low[u] = min(low[u], dfn[v]);
        }
    }
}

vector<pair<int, int>> getBridges(int V, const vector<vector<int>>& adj) {
    vector<int> dfn(V, 0);
    vector<int> low(V, 0);
    vector<pair<int, int>> bridges;
    int time = 0;
    
    for (int i = 0; i < V; i++) {
        if (!dfn[i]) {
            findBridges(i, -1, adj, dfn, low, bridges, time);
        }
    }
    
    return bridges;
}

int main() {
    int V = 5;
    vector<vector<int>> adj(V);
    
    // 构建图
    adj[0].push_back(1);
    adj[1].push_back(0);
    adj[1].push_back(2);
    adj[2].push_back(1);
    adj[2].push_back(3);
    adj[3].push_back(2);
    adj[3].push_back(4);
    adj[4].push_back(3);
    
    vector<pair<int, int>> bridges = getBridges(V, adj);
    
    cout << "桥：" << endl;
    for (const auto& bridge : bridges) {
        cout << bridge.first << " -- " << bridge.second << endl;
    }
    
    return 0;
}

第五章：拓扑排序与有向无环图

5.1 有向无环图的基本概念

有向无环图（Directed Acyclic Graph，DAG）是指没有回路的有向图。DAG在计算机科学中有着广泛的应用，如任务调度、依赖关系分析、编译优化等。

DAG的性质：

DAG中至少存在一个入度为0的顶点和一个出度为0的顶点。
DAG的任意子图也是DAG。
DAG可以进行拓扑排序。

5.2 拓扑排序算法

拓扑排序（Topological Sorting）是将有向无环图中的所有顶点排成一个线性序列，使得对于图中的每条有向边(u, v)，顶点u在序列中都出现在顶点v之前。

拓扑排序的常用算法：

5.2.1 Kahn算法

Kahn算法是一种基于BFS的拓扑排序算法，它的基本思想是：

计算图中每个顶点的入度。
将所有入度为0的顶点加入队列。
当队列不为空时，取出队首顶点，将其加入结果序列，并将其所有邻接顶点的入度减1。如果某个邻接顶点的入度变为0，则将其加入队列。
重复步骤3，直到队列为空。
检查结果序列的长度是否等于图中的顶点数。如果等于，则拓扑排序成功；否则，说明图中存在回路，无法进行拓扑排序。

Kahn算法的C++实现：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<int> topologicalSortKahn(int V, const vector<vector<int>>& adj) {
    vector<int> inDegree(V, 0);
    vector<int> result;
    queue<int> q;
    
    // 计算每个顶点的入度
    for (int u = 0; u < V; u++) {
        for (int v : adj[u]) {
            inDegree[v]++;
        }
    }
    
    // 将所有入度为0的顶点加入队列
    for (int u = 0; u < V; u++) {
        if (inDegree[u] == 0) {
            q.push(u);
        }
    }
    
    // 进行BFS
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        result.push_back(u);
        
        for (int v : adj[u]) {
            inDegree[v]--;
            if (inDegree[v] == 0) {
                q.push(v);
            }
        }
    }
    
    // 检查是否存在回路
    if (result.size() != V) {
        cout << "图中存在回路，无法进行拓扑排序" << endl;
        return {};
    }
    
    return result;
}

int main() {
    int V = 6;
    vector<vector<int>> adj(V);
    
    // 构建图
    adj[5].push_back(2);
    adj[5].push_back(0);
    adj[4].push_back(0);
    adj[4].push_back(1);
    adj[2].push_back(3);
    adj[3].push_back(1);
    
    vector<int> topoOrder = topologicalSortKahn(V, adj);
    
    if (!topoOrder.empty()) {
        cout << "拓扑排序结果：";
        for (int u : topoOrder) {
            cout << u << " ";
        }
        cout << endl;
    }
    
    return 0;
}

5.2.2 DFS-based拓扑排序

基于DFS的拓扑排序算法的基本思想是：

对图进行DFS，记录每个顶点的完成时间。
按照顶点的完成时间从大到小的顺序排列顶点，得到的就是拓扑排序的结果。

DFS-based拓扑排序的C++实现：

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

void dfs(int u, const vector<vector<int>>& adj, vector<bool>& visited, stack<int>& result) {
    visited[u] = true;
    
    for (int v : adj[u]) {
        if (!visited[v]) {
            dfs(v, adj, visited, result);
        }
    }
    
    // 将顶点加入栈中，后序遍历的逆序就是拓扑排序的顺序
    result.push(u);
}

vector<int> topologicalSortDFS(int V, const vector<vector<int>>& adj) {
    vector<bool> visited(V, false);
    stack<int> result;
    
    // 对每个未访问的顶点进行DFS
    for (int u = 0; u < V; u++) {
        if (!visited[u]) {
            dfs(u, adj, visited, result);
        }
    }
    
    // 检查是否存在回路（这里简化处理，实际应用中需要额外检测）
    
    // 将栈中的顶点依次弹出，得到拓扑排序的结果
    vector<int> topoOrder;
    while (!result.empty()) {
        topoOrder.push_back(result.top());
        result.pop();
    }
    
    return topoOrder;
}

int main() {
    int V = 6;
    vector<vector<int>> adj(V);
    
    // 构建图
    adj[5].push_back(2);
    adj[5].push_back(0);
    adj[4].push_back(0);
    adj[4].push_back(1);
    adj[2].push_back(3);
    adj[3].push_back(1);
    
    vector<int> topoOrder = topologicalSortDFS(V, adj);
    
    cout << "拓扑排序结果：";
    for (int u : topoOrder) {
        cout << u << " ";
    }
    cout << endl;
    
    return 0;
}

5.3 拓扑排序的应用

拓扑排序在计算机科学中有广泛的应用，主要包括：

任务调度：在项目管理中，拓扑排序可以用来确定任务的执行顺序，确保每个任务的所有前置任务都已完成。
依赖关系分析：在软件包管理中，拓扑排序可以用来分析软件包之间的依赖关系，确定软件包的安装顺序。
编译优化：在编译器中，拓扑排序可以用来分析变量之间的依赖关系，进行指令重排序优化。
事件驱动系统：在事件驱动系统中，拓扑排序可以用来确定事件的处理顺序，确保事件的处理符合因果关系。

第六章：二分图与匹配算法

6.1 二分图的基本概念

二分图（Bipartite Graph）是指可以将顶点集分成两个不相交的子集U和V，使得图中的每条边都连接U中的一个顶点和V中的一个顶点的图。二分图在匹配问题、资源分配等领域有着广泛的应用。

二分图的性质：

二分图中没有奇数长度的回路。
二分图可以被2-着色，即可以用两种颜色对顶点进行着色，使得相邻的顶点颜色不同。

二分图的判定：可以使用染色法或BFS/DFS来判断一个图是否是二分图。

二分图判定的C++实现（使用BFS）：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

bool isBipartite(int V, const vector<vector<int>>& adj) {
    vector<int> color(V, -1); // -1表示未染色，0和1表示两种不同的颜色
    
    for (int start = 0; start < V; start++) {
        if (color[start] == -1) { // 如果未染色
            queue<int> q;
            q.push(start);
            color[start] = 0;
            
            while (!q.empty()) {
                int u = q.front();
                q.pop();
                
                for (int v : adj[u]) {
                    if (color[v] == -1) { // 未染色，染成相反的颜色
                        color[v] = color[u] ^ 1;
                        q.push(v);
                    } else if (color[v] == color[u]) { // 已经染色，且颜色相同，不是二分图
                        return false;
                    }
                }
            }
        }
    }
    
    return true; // 是二分图
}

int main() {
    int V = 4;
    vector<vector<int>> adj(V);
    
    // 构建图
    adj[0].push_back(1);
    adj[0].push_back(3);
    adj[1].push_back(0);
    adj[1].push_back(2);
    adj[2].push_back(1);
    adj[2].push_back(3);
    adj[3].push_back(0);
    adj[3].push_back(2);
    
    if (isBipartite(V, adj)) {
        cout << "这是一个二分图" << endl;
    } else {
        cout << "这不是一个二分图" << endl;
    }
    
    return 0;
}

6.2 二分图匹配算法

二分图匹配是指在二分图中寻找一个边集，使得这个边集中的任意两条边都没有公共顶点。二分图匹配在资源分配、任务调度等领域有着广泛的应用。

6.2.1 最大匹配问题

最大匹配问题是指在二分图中寻找一个边数最大的匹配。求解最大匹配问题的常用算法有匈牙利算法和Hopcroft-Karp算法。

6.2.2 匈牙利算法

匈牙利算法是一种基于DFS的最大匹配算法，它的基本思想是：对于左部的每个顶点，尝试寻找一条增广路径（一条从该顶点出发，最终到达右部未匹配顶点的路径），如果能够找到，则将这条路径上的匹配边和非匹配边互换，从而增加匹配的边数。

匈牙利算法的C++实现：

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

bool dfs(int u, const vector<vector<int>>& adj, vector<bool>& visited, vector<int>& match) {
    for (int v : adj[u]) {
        if (!visited[v]) {
            visited[v] = true;
            if (match[v] == -1 || dfs(match[v], adj, visited, match)) {
                match[v] = u;
                return true;
            }
        }
    }
    return false;
}

int hungarian(int V, const vector<vector<int>>& adj) {
    vector<int> match(V, -1); // 记录右部顶点匹配的左部顶点
    int result = 0;
    
    for (int u = 0; u < V; u++) {
        vector<bool> visited(V, false);
        if (dfs(u, adj, visited, match)) {
            result++;
        }
    }
    
    return result;
}

int main() {
    int V = 4; // 左部和右部顶点数均为4
    vector<vector<int>> adj(V); // adj[u]表示左部顶点u可以匹配的右部顶点
    
    // 构建二分图
    adj[0].push_back(1);
    adj[0].push_back(2);
    adj[1].push_back(0);
    adj[1].push_back(2);
    adj[2].push_back(3);
    adj[3].push_back(3);
    
    int maxMatch = hungarian(V, adj);
    
    cout << "最大匹配边数：" << maxMatch << endl;
    
    return 0;
}

6.2.3 Hopcroft-Karp算法

Hopcroft-Karp算法是一种基于BFS和DFS的最大匹配算法，它的时间复杂度比匈牙利算法更低，适用于大规模的二分图匹配问题。Hopcroft-Karp算法的基本思想是：每次通过BFS分层，然后通过DFS寻找多条不相交的增广路径，从而一次性增加多个匹配边。

Hopcroft-Karp算法的C++实现：

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

const int INF = 0x3f3f3f3f;

bool bfs(int V, const vector<vector<int>>& adj, vector<int>& pairU, vector<int>& pairV, vector<int>& dist) {
    queue<int> q;
    
    // 初始化距离数组，将所有未匹配的左部顶点加入队列
    for (int u = 0; u < V; u++) {
        if (pairU[u] == -1) {
            dist[u] = 0;
            q.push(u);
        } else {
            dist[u] = INF;
        }
    }
    
    // 初始化右部顶点的距离为INF
    int distV = INF;
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        
        if (dist[u] < distV) {
            for (int v : adj[u]) {
                if (pairV[v] == -1) {
                    distV = dist[u] + 1;
                } else if (dist[pairV[v]] == INF) {
                    dist[pairV[v]] = dist[u] + 1;
                    q.push(pairV[v]);
                }
            }
        }
    }
    
    return distV != INF;
}

bool dfs(int u, const vector<vector<int>>& adj, vector<int>& pairU, vector<int>& pairV, vector<int>& dist) {
    for (int v : adj[u]) {
        if (pairV[v] == -1 || (dist[pairV[v]] == dist[u] + 1 && dfs(pairV[v], adj, pairU, pairV, dist))) {
            pairU[u] = v;
            pairV[v] = u;
            return true;
        }
    }
    
    dist[u] = INF;
    return false;
}

int hopcroftKarp(int V, const vector<vector<int>>& adj) {
    vector<int> pairU(V, -1); // pairU[u]表示左部顶点u匹配的右部顶点
    vector<int> pairV(V, -1); // pairV[v]表示右部顶点v匹配的左部顶点
    vector<int> dist(V); // 记录左部顶点的距离
    int result = 0;
    
    while (bfs(V, adj, pairU, pairV, dist)) {
        for (int u = 0; u < V; u++) {
            if (pairU[u] == -1) {
                if (dfs(u, adj, pairU, pairV, dist)) {
                    result++;
                }
            }
        }
    }
    
    return result;
}

int main() {
    int V = 4; // 左部和右部顶点数均为4
    vector<vector<int>> adj(V); // adj[u]表示左部顶点u可以匹配的右部顶点
    
    // 构建二分图
    adj[0].push_back(1);
    adj[0].push_back(2);
    adj[1].push_back(0);
    adj[1].push_back(2);
    adj[2].push_back(3);
    adj[3].push_back(3);
    
    int maxMatch = hopcroftKarp(V, adj);
    
    cout << "最大匹配边数：" << maxMatch << endl;
    
    return 0;
}

6.3 二分图匹配的应用

二分图匹配在计算机科学和实际生活中有广泛的应用，主要包括：

资源分配问题：将有限的资源分配给不同的任务，确保每个任务都能获得所需的资源。
任务调度问题：安排机器或人员完成不同的任务，确保每个任务都能被完成。
人员匹配问题：根据人员的技能和偏好，将人员分配到合适的岗位。
网络流问题：二分图匹配可以转化为网络流问题，通过最大流算法求解。

第七章：网络流算法

7.1 网络流的基本概念

网络流是指在一个有向图中，从源点到汇点的一种流量分配。网络流问题在通信网络、交通网络、资源分配等领域有着广泛的应用。

网络流的基本概念：

流网络：一个有向图，其中每条边都有一个非负的容量，图中存在一个源点和一个汇点。
流量：在流网络中，从源点到汇点的一种流动，流量必须满足容量约束和流量守恒约束。
容量约束：对于每条边(u, v)，其流量f(u, v)必须满足0 ≤ f(u, v) ≤ c(u, v)，其中c(u, v)是边(u, v)的容量。
流量守恒约束：对于除源点和汇点之外的所有顶点，流入该顶点的流量之和必须等于流出该顶点的流量之和。
最大流：在流网络中，从源点到汇点的最大可能流量。
最小割：在流网络中，将源点和汇点分开的一个边割，其容量之和最小。

7.2 最大流算法

求解最大流问题的常用算法有Ford-Fulkerson算法、Edmonds-Karp算法、Dinic算法等。

7.2.1 Ford-Fulkerson算法

Ford-Fulkerson算法是一种迭代算法，它的基本思想是：每次在剩余网络中寻找一条从源点到汇点的增广路径，然后沿这条路径增加流量，直到无法找到增广路径为止。

Ford-Fulkerson算法的C++实现（使用DFS寻找增广路径）：

#include <iostream>
#include <vector>
#include <cstring>
#include <climits>
using namespace std;

const int INF = INT_MAX;

bool dfs(int u, int t, int minFlow, const vector<vector<int>>& capacity, vector<vector<int>>& flow, vector<bool>& visited, vector<vector<int>>& adj) {
    if (u == t) return true;
    visited[u] = true;
    
    for (int v : adj[u]) {
        if (!visited[v] && capacity[u][v] > flow[u][v]) {
            int currentMinFlow = min(minFlow, capacity[u][v] - flow[u][v]);
            if (dfs(v, t, currentMinFlow, capacity, flow, visited, adj)) {
                flow[u][v] += currentMinFlow;
                flow[v][u] -= currentMinFlow; // 反向边
                return true;
            }
        }
    }
    
    return false;
}

int fordFulkerson(int V, int s, int t, const vector<vector<int>>& capacity, vector<vector<int>>& adj) {
    vector<vector<int>> flow(V, vector<int>(V, 0));
    int maxFlow = 0;
    
    while (true) {
        vector<bool> visited(V, false);
        if (!dfs(s, t, INF, capacity, flow, visited, adj)) {
            break;
        }
        maxFlow++;
    }
    
    return maxFlow;
}

int main() {
    int V = 6;
    int s = 0; // 源点
    int t = 5; // 汇点
    
    // 构建容量矩阵
    vector<vector<int>> capacity(V, vector<int>(V, 0));
    capacity[0][1] = 16;
    capacity[0][2] = 13;
    capacity[1][2] = 10;
    capacity[1][3] = 12;
    capacity[2][1] = 4;
    capacity[2][4] = 14;
    capacity[3][2] = 9;
    capacity[3][5] = 20;
    capacity[4][3] = 7;
    capacity[4][5] = 4;
    
    // 构建邻接表
    vector<vector<int>> adj(V);
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            if (capacity[i][j] > 0) {
                adj[i].push_back(j);
                adj[j].push_back(i); // 反向边
            }
        }
    }
    
    int maxFlow = fordFulkerson(V, s, t, capacity, adj);
    
    cout << "最大流：" << maxFlow << endl;
    
    return 0;
}

7.2.2 Edmonds-Karp算法

Edmonds-Karp算法是Ford-Fulkerson算法的一个特例，它使用BFS来寻找增广路径，从而保证了算法的时间复杂度为O(VE²)。

Edmonds-Karp算法的C++实现：

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <climits>
using namespace std;

const int INF = INT_MAX;

int edmondsKarp(int V, int s, int t, vector<vector<int>>& capacity, vector<vector<int>>& adj) {
    vector<vector<int>> flow(V, vector<int>(V, 0));
    int maxFlow = 0;
    
    while (true) {
        vector<int> parent(V, -1);
        vector<bool> visited(V, false);
        queue<int> q;
        
        q.push(s);
        visited[s] = true;
        
        // BFS寻找增广路径
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            
            for (int v : adj[u]) {
                if (!visited[v] && capacity[u][v] > flow[u][v]) {
                    parent[v] = u;
                    visited[v] = true;
                    q.push(v);
                    if (v == t) break;
                }
            }
        }
        
        // 如果无法到达汇点，结束算法
        if (parent[t] == -1) break;
        
        // 计算增广路径上的最小剩余容量
        int minFlow = INF;
        for (int v = t; v != s; v = parent[v]) {
            int u = parent[v];
            minFlow = min(minFlow, capacity[u][v] - flow[u][v]);
        }
        
        // 更新流量
        for (int v = t; v != s; v = parent[v]) {
            int u = parent[v];
            flow[u][v] += minFlow;
            flow[v][u] -= minFlow; // 反向边
        }
        
        maxFlow += minFlow;
    }
    
    return maxFlow;
}

int main() {
    int V = 6;
    int s = 0; // 源点
    int t = 5; // 汇点
    
    // 构建容量矩阵
    vector<vector<int>> capacity(V, vector<int>(V, 0));
    capacity[0][1] = 16;
    capacity[0][2] = 13;
    capacity[1][2] = 10;
    capacity[1][3] = 12;
    capacity[2][1] = 4;
    capacity[2][4] = 14;
    capacity[3][2] = 9;
    capacity[3][5] = 20;
    capacity[4][3] = 7;
    capacity[4][5] = 4;
    
    // 构建邻接表
    vector<vector<int>> adj(V);
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            if (capacity[i][j] > 0) {
                adj[i].push_back(j);
                adj[j].push_back(i); // 反向边
            }
        }
    }
    
    int maxFlow = edmondsKarp(V, s, t, capacity, adj);
    
    cout << "最大流：" << maxFlow << endl;
    
    return 0;
}

7.2.3 Dinic算法

Dinic算法是一种高效的最大流算法，它的基本思想是：首先通过BFS对剩余网络进行分层，然后通过DFS在分层网络中寻找阻塞流（无法再增广的流），重复这两个步骤直到无法找到增广路径为止。Dinic算法的时间复杂度为O(V²E)，在实际应用中比Edmonds-Karp算法效率更高。

Dinic算法的C++实现：

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <climits>
using namespace std;

const int INF = INT_MAX;

bool bfs(int V, int s, int t, const vector<vector<int>>& capacity, const vector<vector<int>>& adj, vector<int>& level) {
    fill(level.begin(), level.end(), -1);
    queue<int> q;
    
    level[s] = 0;
    q.push(s);
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        
        for (int v : adj[u]) {
            if (level[v] == -1 && capacity[u][v] > 0) {
                level[v] = level[u] + 1;
                q.push(v);
                if (v == t) return true;
            }
        }
    }
    
    return false;
}

int dfs(int u, int t, int minFlow, vector<vector<int>>& capacity, const vector<vector<int>>& adj, vector<int>& level, vector<int>& iter) {
    if (u == t) return minFlow;
    
    for (int& i = iter[u]; i < adj[u].size(); i++) {
        int v = adj[u][i];
        if (level[v] > level[u] && capacity[u][v] > 0) {
            int flow = dfs(v, t, min(minFlow, capacity[u][v]), capacity, adj, level, iter);
            if (flow > 0) {
                capacity[u][v] -= flow;
                capacity[v][u] += flow; // 反向边
                return flow;
            }
        }
    }
    
    return 0;
}

int dinic(int V, int s, int t, vector<vector<int>>& capacity, const vector<vector<int>>& adj) {
    int maxFlow = 0;
    vector<int> level(V);
    
    while (bfs(V, s, t, capacity, adj, level)) {
        vector<int> iter(V, 0);
        int flow;
        while ((flow = dfs(s, t, INF, capacity, adj, level, iter)) > 0) {
            maxFlow += flow;
        }
    }
    
    return maxFlow;
}

int main() {
    int V = 6;
    int s = 0; // 源点
    int t = 5; // 汇点
    
    // 构建容量矩阵
    vector<vector<int>> capacity(V, vector<int>(V, 0));
    capacity[0][1] = 16;
    capacity[0][2] = 13;
    capacity[1][2] = 10;
    capacity[1][3] = 12;
    capacity[2][1] = 4;
    capacity[2][4] = 14;
    capacity[3][2] = 9;
    capacity[3][5] = 20;
    capacity[4][3] = 7;
    capacity[4][5] = 4;
    
    // 构建邻接表
    vector<vector<int>> adj(V);
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            if (capacity[i][j] > 0) {
                adj[i].push_back(j);
                adj[j].push_back(i); // 反向边
            }
        }
    }
    
    int maxFlow = dinic(V, s, t, capacity, adj);
    
    cout << "最大流：" << maxFlow << endl;
    
    return 0;
}

7.3 最小割问题

根据最大流最小割定理，在一个流网络中，最大流的值等于最小割的容量。因此，可以通过求解最大流来得到最小割。

寻找最小割的C++实现（基于Dinic算法）：

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <climits>
#include <algorithm>
using namespace std;

const int INF = INT_MAX;

bool bfs(int V, int s, int t, const vector<vector<int>>& capacity, const vector<vector<int>>& adj, vector<int>& level) {
    fill(level.begin(), level.end(), -1);
    queue<int> q;
    
    level[s] = 0;
    q.push(s);
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        
        for (int v : adj[u]) {
            if (level[v] == -1 && capacity[u][v] > 0) {
                level[v] = level[u] + 1;
                q.push(v);
                if (v == t) return true;
            }
        }
    }
    
    return false;
}

int dfs(int u, int t, int minFlow, vector<vector<int>>& capacity, const vector<vector<int>>& adj, vector<int>& level, vector<int>& iter) {
    if (u == t) return minFlow;
    
    for (int& i = iter[u]; i < adj[u].size(); i++) {
        int v = adj[u][i];
        if (level[v] > level[u] && capacity[u][v] > 0) {
            int flow = dfs(v, t, min(minFlow, capacity[u][v]), capacity, adj, level, iter);
            if (flow > 0) {
                capacity[u][v] -= flow;
                capacity[v][u] += flow; // 反向边
                return flow;
            }
        }
    }
    
    return 0;
}

int dinic(int V, int s, int t, vector<vector<int>>& capacity, const vector<vector<int>>& adj) {
    int maxFlow = 0;
    vector<int> level(V);
    
    while (bfs(V, s, t, capacity, adj, level)) {
        vector<int> iter(V, 0);
        int flow;
        while ((flow = dfs(s, t, INF, capacity, adj, level, iter)) > 0) {
            maxFlow += flow;
        }
    }
    
    return maxFlow;
}

void findMinCut(int V, int s, const vector<vector<int>>& capacity, const vector<vector<int>>& adj, vector<bool>& visited) {
    queue<int> q;
    q.push(s);
    visited[s] = true;
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        
        for (int v : adj[u]) {
            if (!visited[v] && capacity[u][v] > 0) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
}

int main() {
    int V = 6;
    int s = 0; // 源点
    int t = 5; // 汇点
    
    // 构建容量矩阵
    vector<vector<int>> capacity(V, vector<int>(V, 0));
    capacity[0][1] = 16;
    capacity[0][2] = 13;
    capacity[1][2] = 10;
    capacity[1][3] = 12;
    capacity[2][1] = 4;
    capacity[2][4] = 14;
    capacity[3][2] = 9;
    capacity[3][5] = 20;
    capacity[4][3] = 7;
    capacity[4][5] = 4;
    
    // 构建邻接表
    vector<vector<int>> adj(V);
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            if (capacity[i][j] > 0) {
                adj[i].push_back(j);
                adj[j].push_back(i); // 反向边
            }
        }
    }
    
    // 深拷贝容量矩阵，因为dinic算法会修改容量矩阵
    vector<vector<int>> originalCapacity = capacity;
    
    int maxFlow = dinic(V, s, t, capacity, adj);
    cout << "最大流：" << maxFlow << endl;
    
    // 寻找最小割
    vector<bool> visited(V, false);
    findMinCut(V, s, capacity, adj, visited);
    
    cout << "最小割的边：" << endl;
    int minCutCapacity = 0;
    for (int u = 0; u < V; u++) {
        if (visited[u]) {
            for (int v : adj[u]) {
                if (!visited[v] && originalCapacity[u][v] > 0) {
                    cout << u << " -> " << v << " (容量：" << originalCapacity[u][v] << ")" << endl;
                    minCutCapacity += originalCapacity[u][v];
                }
            }
        }
    }
    cout << "最小割的容量：" << minCutCapacity << endl;
    
    return 0;
}

7.4 最小费用流问题

最小费用流问题是指在流网络中，找到一个最大流，使得流的总费用最小。最小费用流问题的常用算法有SPFA寻找最短增广路径算法、Dijkstra寻找最短增广路径算法等。

使用SPFA寻找最短增广路径的最小费用流算法的C++实现：

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <climits>
using namespace std;

const int INF = INT_MAX;

struct Edge {
    int to;
    int capacity;
    int cost;
    int rev;
    Edge(int t, int c, int co, int r) : to(t), capacity(c), cost(co), rev(r) {}
};

void addEdge(vector<vector<Edge>>& graph, int from, int to, int capacity, int cost) {
    graph[from].emplace_back(to, capacity, cost, graph[to].size());
    graph[to].emplace_back(from, 0, -cost, graph[from].size() - 1);
}

pair<int, int> minCostFlow(vector<vector<Edge>>& graph, int V, int s, int t, int maxFlow) {
    vector<int> h(V, 0); // 势函数，用于Johnson算法
    vector<int> prevv(V);
    vector<int> preve(V);
    int flow = 0;
    int cost = 0;
    
    while (flow < maxFlow) {
        vector<int> dist(V, INF);
        vector<bool> inQueue(V, false);
        queue<int> q;
        
        dist[s] = 0;
        q.push(s);
        inQueue[s] = true;
        
        // SPFA寻找最短增广路径
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            inQueue[u] = false;
            
            for (int i = 0; i < graph[u].size(); i++) {
                Edge& edge = graph[u][i];
                if (edge.capacity > 0 && dist[edge.to] > dist[u] + edge.cost + h[u] - h[edge.to]) {
                    dist[edge.to] = dist[u] + edge.cost + h[u] - h[edge.to];
                    prevv[edge.to] = u;
                    preve[edge.to] = i;
                    if (!inQueue[edge.to]) {
                        q.push(edge.to);
                        inQueue[edge.to] = true;
                    }
                }
            }
        }
        
        if (dist[t] == INF) break; // 无法再增广
        
        // 更新势函数
        for (int v = 0; v < V; v++) {
            h[v] += dist[v];
        }
        
        // 计算增广路径上的最小剩余容量
        int d = maxFlow - flow;
        for (int v = t; v != s; v = prevv[v]) {
            d = min(d, graph[prevv[v]][preve[v]].capacity);
        }
        
        // 更新流量和费用
        flow += d;
        cost += d * h[t];
        
        // 更新剩余容量
        for (int v = t; v != s; v = prevv[v]) {
            Edge& edge = graph[prevv[v]][preve[v]];
            edge.capacity -= d;
            graph[v][edge.rev].capacity += d;
        }
    }
    
    return {flow, cost};
}

int main() {
    int V = 4;
    int s = 0; // 源点
    int t = 3; // 汇点
    int maxFlow = 5; // 最大流
    
    vector<vector<Edge>> graph(V);
    
    // 添加边
    addEdge(graph, 0, 1, 10, 2);
    addEdge(graph, 0, 2, 2, 4);
    addEdge(graph, 1, 2, 6, 1);
    addEdge(graph, 1, 3, 6, 3);
    addEdge(graph, 2, 3, 10, 2);
    
    pair<int, int> result = minCostFlow(graph, V, s, t, maxFlow);
    
    cout << "最小费用最大流的流量：" << result.first << endl;
    cout << "最小费用最大流的费用：" << result.second << endl;
    
    return 0;
}

第八章：图论高级算法与技巧

8.1 树的高级算法

8.1.1 树链剖分

树链剖分是一种将树分割成若干条链，以便在树上进行高效查询和更新操作的算法。树链剖分的主要思想是将树分割成若干条重链，使得树中的任意路径都可以被分解为不超过O(log n)条重链的拼接。

树链剖分的基本步骤：

第一次DFS：计算每个节点的父节点、深度、子树大小和重儿子（子树大小最大的子节点）。
第二次DFS：为每个节点分配链顶（所在重链的顶端节点）和DFS序（用于将树映射到线段树）。

树链剖分的C++实现：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 10005;

vector<int> adj[MAXN]; // 树的邻接表
int fa[MAXN]; // 父节点
int dep[MAXN]; // 深度
int siz[MAXN]; // 子树大小
int son[MAXN]; // 重儿子
int top[MAXN]; // 链顶
int dfn[MAXN]; // DFS序
int rnk[MAXN]; // 逆DFS序
int cnt = 0; // DFS序计数器

// 第一次DFS，计算父节点、深度、子树大小和重儿子
void dfs1(int u, int f) {
    fa[u] = f;
    dep[u] = dep[f] + 1;
    siz[u] = 1;
    son[u] = 0;
    
    for (int v : adj[u]) {
        if (v != f) {
            dfs1(v, u);
            siz[u] += siz[v];
            if (siz[v] > siz[son[u]]) {
                son[u] = v;
            }
        }
    }
}

// 第二次DFS，分配链顶和DFS序
void dfs2(int u, int topf) {
    top[u] = topf;
    dfn[u] = ++cnt;
    rnk[cnt] = u;
    
    if (son[u]) { // 先处理重儿子
        dfs2(son[u], topf);
        for (int v : adj[u]) {
            if (v != fa[u] && v != son[u]) {
                dfs2(v, v); // 轻儿子作为新链的链顶
            }
        }
    }
}

// 线段树的实现（此处省略）

// 查询树中两个节点之间的路径上的最大值
int queryPath(int u, int v) {
    int res = 0;
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        // 在线段树中查询区间[dfn[top[u]], dfn[u]]的最大值
        // res = max(res, segQuery(1, 1, cnt, dfn[top[u]], dfn[u]));
        u = fa[top[u]];
    }
    if (dep[u] > dep[v]) swap(u, v);
    // 在线段树中查询区间[dfn[u], dfn[v]]的最大值
    // res = max(res, segQuery(1, 1, cnt, dfn[u], dfn[v]));
    return res;
}

int main() {
    int n; // 节点数
    cin >> n;
    
    // 构建树
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    // 进行树链剖分
    dfs1(1, 0);
    dfs2(1, 1);
    
    // 后续操作（如查询路径上的最大值等）
    
    return 0;
}

8.1.2 动态树（Link-Cut Tree）

动态树是一种数据结构，用于处理动态树连接问题，支持动态地连接两个树、断开树中的一条边、查询树中的路径信息等操作。Link-Cut Tree是一种常见的动态树实现方式。

Link-Cut Tree的基本操作：

access(u)：建立从根到u的路径的偏爱路径。
makeroot(u)：将u设置为树的根。
findroot(u)：找到u所在树的根。
split(u, v)：提取u到v的路径。
link(u, v)：连接u和v所在的树，要求u和v不在同一棵树中，且u是所在树的根。
cut(u, v)：断开u和v之间的边，要求u和v直接相连。

Link-Cut Tree的C++实现：

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 10005;

struct Node {
    Node *ch[2], *fa;
    bool rev;
    int val, sum; // 节点的值和子树的和
    Node() : fa(nullptr), rev(false), val(0), sum(0) {
        ch[0] = ch[1] = nullptr;
    }
    bool isRoot() {
        return fa == nullptr || (fa->ch[0] != this && fa->ch[1] != this);
    }
    void pushUp() {
        sum = val;
        if (ch[0]) sum += ch[0]->sum;
        if (ch[1]) sum += ch[1]->sum;
    }
    void pushDown() {
        if (rev) {
            swap(ch[0], ch[1]);
            if (ch[0]) ch[0]->rev ^= 1;
            if (ch[1]) ch[1]->rev ^= 1;
            rev = false;
        }
    }
} T[MAXN];

// 旋转操作
void rotate(Node *x) {
    Node *y = x->fa, *z = y->fa;
    int k = (y->ch[1] == x);
    if (!y->isRoot()) z->ch[z->ch[1] == y] = x;
    x->fa = z;
    y->ch[k] = x->ch[k^1];
    if (x->ch[k^1]) x->ch[k^1]->fa = y;
    x->ch[k^1] = y;
    y->fa = x;
    y->pushUp();
    x->pushUp();
}

// 维护路径上的标记
void splay(Node *x) {
    // 记录路径上的节点，以便pushDown
    static Node *stk[MAXN];
    int top = 0;
    stk[top++] = x;
    for (Node *u = x; !u->isRoot(); u = u->fa) {
        stk[top++] = u->fa;
    }
    while (top--) stk[top]->pushDown();
    
    while (!x->isRoot()) {
        Node *y = x->fa, *z = y->fa;
        if (!y->isRoot()) {
            rotate((y->ch[0] == x) ^ (z->ch[0] == y) ? x : y);
        }
        rotate(x);
    }
}

// 建立从根到x的偏爱路径
void access(Node *x) {
    for (Node *pre = nullptr; x; pre = x, x = x->fa) {
        splay(x);
        x->ch[1] = pre;
        x->pushUp();
    }
}

// 将x设置为树的根
void makeroot(Node *x) {
    access(x);
    splay(x);
    x->rev ^= 1;
}

// 找到x所在树的根
Node* findroot(Node *x) {
    access(x);
    splay(x);
    while (x->ch[0]) {
        x->pushDown();
        x = x->ch[0];
    }
    splay(x); // 确保下次操作的效率
    return x;
}

// 提取x到y的路径
void split(Node *x, Node *y) {
    makeroot(x);
    access(y);
    splay(y);
}

// 连接x和y所在的树
void link(Node *x, Node *y) {
    makeroot(x);
    if (findroot(y) != x) {
        x->fa = y;
    }
}

// 断开x和y之间的边
void cut(Node *x, Node *y) {
    makeroot(x);
    if (findroot(y) == x && y->fa == x && !y->ch[0]) {
        y->fa = nullptr;
        x->ch[1] = nullptr;
        x->pushUp();
    }
}

// 查询x到y路径上的值的和
int querySum(Node *x, Node *y) {
    split(x, y);
    return y->sum;
}

int main() {
    int n; // 节点数
    cin >> n;
    
    // 初始化节点的值
    for (int i = 1; i <= n; i++) {
        cin >> T[i].val;
        T[i].sum = T[i].val;
    }
    
    // 后续操作（如link、cut、查询等）
    
    return 0;
}

8.2 平面图算法

平面图是指可以嵌入平面上，且没有边相交的图。平面图在地图绘制、集成电路设计等领域有着广泛的应用。

8.2.1 平面图的判定

平面图的判定可以使用Euler公式或Kuratowski定理。Euler公式指出，对于一个连通的平面图，有V - E + F = 2，其中V是顶点数，E是边数，F是面数。Kuratowski定理指出，一个图是平面图当且仅当它不包含K₅（5个顶点的完全图）或K₃,₃（二分图，左右部各有3个顶点，且所有顶点之间都有边相连）作为子图。

8.2.2 平面图的对偶图

平面图的对偶图是指将平面图中的每个面映射为一个顶点，将平面图中的每条边映射为一条边的图。对偶图在平面图的染色问题中有着重要的应用。

8.3 图的染色问题

图的染色问题是指用最少的颜色对图中的顶点或边进行着色，使得相邻的顶点或边颜色不同。图的染色问题在调度问题、频率分配、模式识别等领域有着广泛的应用。

8.3.1 顶点染色

顶点染色是指用最少的颜色对图中的顶点进行着色，使得相邻的顶点颜色不同。顶点染色的最小颜色数称为图的色数。对于一般图来说，顶点染色问题是NP难的，但对于一些特殊图（如二分图、平面图等），存在多项式时间算法。

8.3.2 边染色

边染色是指用最少的颜色对图中的边进行着色，使得相邻的边颜色不同。边染色的最小颜色数称为图的边色数。根据Vizing定理，对于任何简单图，其边色数等于其最大度数或最大度数加1。

第九章：图论算法实战训练

9.1 图论算法在IO竞赛中的常见题型

9.1.1 路径问题

路径问题是IO竞赛中最常见的图论问题之一，主要包括：

最短路径问题：如Dijkstra算法、Bellman-Ford算法、SPFA算法、Floyd-Warshall算法等的应用。
最长路径问题：在有向无环图中可以用拓扑排序求解，在一般图中是NP难的。
路径计数问题：统计从一个顶点到另一个顶点的路径数目。
路径覆盖问题：如最小路径覆盖问题，可以转化为二分图匹配问题求解。

9.1.2 连通性问题

连通性问题也是IO竞赛中的常见图论问题，主要包括：

判断图的连通性：使用DFS或BFS判断无向图是否连通。
强连通分量分解：如Kosaraju算法、Tarjan算法、Gabow算法等的应用。
双连通分量分解：如寻找割点和桥，以及双连通分量分解。
点双连通分量和边双连通分量：在网络设计中有着重要的应用。

9.1.3 匹配问题

匹配问题在IO竞赛中也经常出现，主要包括：

二分图最大匹配：如匈牙利算法、Hopcroft-Karp算法等的应用。
二分图最佳匹配：如Kuhn-Munkres算法（KM算法）等的应用。
一般图匹配：如Edmonds算法等的应用，但在IO竞赛中较少出现。

9.1.4 网络流问题

网络流问题在IO竞赛中是较为高级的图论问题，主要包括：

最大流问题：如Dinic算法、Edmonds-Karp算法等的应用。
最小割问题：根据最大流最小割定理，可以通过求解最大流来得到最小割。
最小费用流问题：如使用SPFA或Dijkstra寻找最短增广路径的算法的应用。
有上下界的网络流问题：如有源汇的有上下界最大流、有源汇的有上下界最小流等。

9.2 图论算法实战技巧

9.2.1 图的表示方法选择

在IO竞赛中，选择合适的图的表示方法对于算法的效率至关重要。一般来说：

对于稠密图（边数接近顶点数的平方），邻接矩阵的效率更高。
对于稀疏图（边数远小于顶点数的平方），邻接表的效率更高。
对于需要频繁添加和删除边的情况，邻接表或边列表的效率更高。

9.2.2 算法优化技巧

在IO竞赛中，为了提高算法的效率，常常需要对算法进行优化，主要包括：

使用优先队列优化：如Dijkstra算法的优先队列优化、Prim算法的优先队列优化等。
使用位运算优化：如在状态压缩的动态规划中使用位运算。
使用记忆化搜索优化：如在递归算法中使用记忆化搜索避免重复计算。
使用剪枝优化：如在DFS中使用剪枝减少搜索空间。

9.2.3 常见错误与调试技巧

在IO竞赛中，图论算法常常容易出现错误，主要包括：

数组越界：在定义数组大小时，应确保数组足够大，以避免数组越界。
初始化错误：如距离数组、父节点数组等的初始化错误。
循环条件错误：如在BFS或DFS中，循环条件的错误可能导致死循环或提前终止。
逻辑错误：如在算法的实现中，逻辑错误可能导致算法的结果不正确。

调试图论算法的常用技巧包括：

输出中间结果：如在算法的关键步骤输出中间结果，以便观察算法的执行过程。
构造小数据测试：使用小数据构造测试用例，手动计算结果，然后与算法的输出进行比较。
使用断言：在算法的关键位置使用断言，以便在条件不满足时及时发现错误。
检查边界条件：如空图、单顶点图、完全图等边界条件的处理是否正确。

9.3 实战训练建议

掌握基础算法：首先要熟练掌握图论的基础算法，如DFS、BFS、Dijkstra算法、Kruskal算法、Prim算法等。
理解算法原理：不仅要记住算法的代码，更要理解算法的原理和思想，这样才能在遇到新问题时灵活运用。
多做练习题：通过做大量的练习题来巩固所学的算法，提高解题能力。可以从简单的题目开始，逐渐过渡到复杂的题目。
总结解题经验：在做题的过程中，要注意总结解题经验，如常见的图论模型、常用的优化技巧等。
参加模拟比赛：参加模拟比赛可以提高解题速度和应变能力，同时也可以了解最新的竞赛动态和题型。

结论

图论是IO竞赛中的重要内容，掌握图论算法对于在IO竞赛中取得好成绩至关重要。本文从图的基本概念出发，深入解析了各类图论算法的原理和应用，包括最短路径算法、最小生成树算法、图的连通性算法、拓扑排序与有向无环图、二分图与匹配算法、网络流算法以及图论高级算法与技巧等。通过学习和实践这些算法，相信读者一定能够在IO竞赛中取得优异的成绩。

图论算法学习路径图

基础概念 → 图的表示 → 遍历算法 → 最短路径算法 → 最小生成树算法 → 连通性算法 → 拓扑排序 → 二分图匹配 → 网络流 → 高级算法

思考与讨论

在实际应用中，如何根据图的特点选择合适的最短路径算法？
最小生成树的两种经典算法（Kruskal算法和Prim算法）各有什么优缺点？在什么情况下应该选择哪种算法？
如何将实际问题转化为图论模型，从而利用图论算法求解？
在IO竞赛中，如何高效调试图论算法的代码？
图论算法在人工智能、大数据等领域有哪些应用？

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-09-20，如有侵权请联系 cloudcommunity@tencent.com 删除

排序

算法

int

vector

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！