图论基础知识

基础知识

树与图的存储

在算法竞赛或工程中，图通常有两种常见的存储方式：邻接矩阵 和 邻接表。

• 邻接矩阵：适合稠密图（边接近 n^2），空间消耗大 O(n^2))，查询快。
• 邻接表：适合稀疏图（边较少），存储紧凑 O(n+m)，是主流做法。

以下是 邻接表存储模板：

const int N = 10000, M = N * 2; // N是点数，M是边数
int e[M], ne[M], h[N], w[M];    // e存储节点，ne存储next指针，h存储表头，w存储边权
int idx;

void add(int a, int b, int c) {
    e[idx] = b;        // 边 a -> b
    w[idx] = c;        // 边权
    ne[idx] = h[a];    // 指向上一条边
    h[a] = idx++;      // 更新表头
}

• e[idx] 表示边的终点。
• w[idx] 表示边的权重。
• ne[idx] 表示同一个起点的上一条边（链式前向星）。
• h[a] 表示点 a 的邻接表的表头。
• idx 为边的计数器，每次插入新边自增。

👉 常用套路：存无向图时要调用 add(a, b, w); add(b, a, w);。

树与图的关系

• 树（Tree） 是一种特殊的图：
  1. 无环；
  2. 连通；
  3. 有 n−1 条边（对于 n 个节点）。
• 有向无环图（DAG, Directed Acyclic Graph）
  DAG 中不存在环，可以定义拓扑序列。
  • 拓扑序列：若图中存在一条有向边 u→v，则在序列中 u一定位于 v前面。

度（Degree）

• 入度（In-degree）：有多少条边指向该点。
• 出度（Out-degree）：从该点出发有多少条边。

在 有向图 中经常用到入度信息，特别是拓扑排序。

拓扑排序（Topological Sorting）

直观理解

拓扑序就是按照依赖关系排队。例如：

• 学习计划中，必须先学「数据结构」才能学「图论」。
• 先修课程完成，后修课程才能进行。

算法思路（Kahn 算法）

1. 计算所有节点的入度，存到数组 d[]。
2. 找出所有入度为 0 的点，入队。
3. 不断出队：
   • 将该点加入拓扑序列；
   • 删除它发出的所有边，相邻点入度减 1；
   • 若某个点入度变为 0，则入队。
4. 循环直到队列为空。

性质

• 如果图中有环，拓扑排序无法包含所有节点。
• 无环图（DAG）一定至少存在一个入度为 0 的点。

代码模板

vector<int> topo_sort(int n, vector<vector<int>>& edges) {
    vector<int> indeg(n, 0);     // 入度
    vector<vector<int>> g(n);    // 邻接表
    for (auto& e : edges) {
        g[e[0]].push_back(e[1]);
        indeg[e[1]]++;
    }

    queue<int> q;
    for (int i = 0; i < n; i++)
        if (indeg[i] == 0) q.push(i);

    vector<int> res;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        res.push_back(u);
        for (int v : g[u]) {
            if (--indeg[v] == 0)
                q.push(v);
        }
    }
    return res; // 若 res.size() < n，则图中有环
}

总结

• 树是无环连通图，边数是 n−1。
• 图的存储常用邻接表（链式前向星）。
• DAG 的关键算法是拓扑排序。
• 拓扑排序保证「依赖在前，结果在后」。