图论概述

什么是图论

【图论】是数学的一个分支，研究的对象是图（Graph），图是由若干给定的点（顶点）及连接两点的边所构成的图形。在计算机科学中，图是一种抽象数据类型，用于实现数学中图论的无向图和有向图概念。

图的基本概念

1. 顶点（Vertex）：图中的基本元素，也称为节点。
2. 边（Edge）：连接两个顶点的线段。
3. 有向图（Directed Graph）：边有方向的图。
4. 无向图（Undirected Graph）：边没有方向的图。
5. 权重（Weight）：赋予边的数值，表示从一个顶点到另一个顶点的代价。
6. 度（Degree）：与顶点相关联的边的数量。
   • 入度（In-degree）：指向该顶点的边的数量。
   • 出度（Out-degree）：从该顶点出发的边的数量。
7. 路径（Path）：从一个顶点到另一个顶点经过的边的序列。
8. 环（Cycle）：起点和终点相同的路径。
9. 连通图（Connected Graph）：任意两个顶点之间都存在路径的无向图。
10. 强连通图（Strongly Connected Graph）：任意两个顶点之间都存在有向路径的有向图。

图论在ACM竞赛中的应用

在ACM竞赛中，图论是一个非常重要的算法分支，常见的应用包括：

1. 最短路径问题：求解从一个顶点到另一个顶点的最短路径。

   • Dijkstra算法
   • Bellman-Ford算法
   • Floyd-Warshall算法

2. 最小生成树问题：求解连接所有顶点的总权重最小的树。

   • Kruskal算法
   • Prim算法

3. 网络流问题：求解从源点到汇点的最大流量。

   • Ford-Fulkerson算法
   • Edmonds-Karp算法
   • Dinic算法

4. 拓扑排序：对有向无环图的顶点进行排序，使得每个顶点的所有前驱顶点都排在该顶点之前。

5. 二分图匹配：在二分图中找到最大匹配。

   • Hungarian算法
   • Hopcroft-Karp算法

图论算法的时间复杂度

解题技巧

1. 图的表示方法选择：

   • 邻接矩阵：适用于稠密图，边的查询时间为O(1)
   • 邻接表：适用于稀疏图，节省空间

2. 问题转化：

   • 许多实际问题可以转化为图论问题求解
   • 识别问题中的"点"和"边"是关键

3. 算法选择：

   • 根据图的性质和问题要求选择合适的算法
   • 注意时间和空间复杂度的约束

典型例题

例题1：最短路径问题

// Dijkstra算法求解单源最短路径
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

typedef pair<int, int> pii; // first: 距离, second: 顶点

void dijkstra(vector<vector<pii>>& graph, int start, vector<int>& dist) {
    int n = graph.size();
    dist.assign(n, INT_MAX);
    dist[start] = 0;

    // 优先队列，按距离排序（小顶堆）
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, start});

    while (!pq.empty()) {
        int d = pq.top().first;  // 当前距离
        int u = pq.top().second; // 当前顶点
        pq.pop();

        // 如果已经处理过该距离更短的路径，则跳过
        if (d > dist[u]) continue;

        // 遍历所有相邻顶点
        for (auto& edge : graph[u]) {
            int v = edge.first;     // 相邻顶点
            int weight = edge.second; // 边权重

            // 松弛操作
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }
}

例题2：拓扑排序

// 拓扑排序
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<int> topologicalSort(vector<vector<int>>& graph, vector<int>& inDegree) {
    int n = graph.size();
    vector<int> result;
    queue<int> q;

    // 将所有入度为0的顶点加入队列
    for (int i = 0; i < n; i++) {
        if (inDegree[i] == 0) {
            q.push(i);
        }
    }

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        result.push_back(u);

        // 删除从u出发的所有边
        for (int v : graph[u]) {
            // 将v的入度减1
            if (--inDegree[v] == 0) {
                // 如果v的入度变为0，则将v加入队列
                q.push(v);
            }
        }
    }

    // 如果结果的大小小于顶点数，说明图中有环
    return (result.size() == n) ? result : vector<int>();
}

练习题推荐

1. 最短路径类问题：

   • POJ 3259 - Wormholes (负环检测，Bellman-Ford)
   • POJ 1860 - Currency Exchange (判断正环，Bellman-Ford)

2. 最小生成树类问题：

   • POJ 1251 - Jungle Roads (Kruskal算法)
   • POJ 1287 - Networking (Prim算法)

3. 拓扑排序类问题：

   • POJ 1094 - Sorting It All Out (拓扑排序)
   • LeetCode 210 - Course Schedule II (课程安排问题)

4. 二分图类问题：

   • POJ 3041 - Asteroids (二分图最大匹配)
   • POJ 1325 - Machine Schedule (二分图最大匹配)

总结

图论是算法竞赛中最重要的部分之一，掌握图的基本概念和常见算法对于解决复杂问题至关重要。在学习过程中，应注重算法的实现和时间复杂度分析，同时通过大量练习题巩固所学知识。

在接下来的章节中，我们将深入探讨各种图论算法的实现和应用。