图论基础（图的存储、拓扑排序）

目录¶

图的存储
拓扑排序

1 图的存储¶

1.1 邻接矩阵¶

使用一个二维数组 adj 来存边，其中 adj[u][v] 为 1 表示存在 \(u\) 到 \(v\) 的边，为 0 表示不存在。如果是带边权的图，可以在 adj[u][v] 中存储 \(u\) 到 \(v\) 的边权。

#include <iostream>
#include <vector>

using namespace std;

int n, m;
vector<bool> vis;
vector<vector<bool>> adj;

bool find_edge(int u, int v) { return adj[u][v]; }

void dfs(int u) {
    if (vis[u]) return;
    vis[u] = true;
    for (int v = 1; v <= n; ++v) {
        if (adj[u][v]) {
            dfs(v);
        }
    }
}

int main() {
    cin >> n >> m;

    vis.resize(n + 1);
    adj.resize(n + 1, vector<bool>(n + 1));

    for (int i = 1; i <= m; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u][v] = true;
    }

    return 0;
}

vis = [False] * (n + 1)
adj = [[False] * (n + 1) for _ in range(n + 1)]

for i in range(1, m + 1):
    u, v = map(int, input().split())
    adj[u][v] = True

def find_edge(u, v):
    return adj[u][v]

def dfs(u):
    if vis[u]:
        return
    vis[u] = True
    for v in range(1, n + 1):
        if adj[u][v]:
            dfs(v)

邻接矩阵在稀疏图上效率很低，尤其是在点数较多的图上，空间无法承受，所以一般只会在稠密图上使用邻接矩阵。

1.2 邻接表¶

使用一个支持动态增加元素的数据结构构成的数组，如 vector<int> adj[n + 1] 来存边，其中 adj[u] 存储的是点 u 的所有出边的相关信息（终点，边权等）。

#include <iostream>
#include <vector>

using namespace std;

int n, m;
vector<bool> vis;
vector<vector<int>> adj;

bool find_edge(int u, int v) {
    for (int i = 0; i < adj[u].size(); ++i) {
        if (adj[u][i] == v) {
            return true;
        }
    }
    return false;
}

void dfs(int u) {
    if (vis[u]) return;
    vis[u] = true;
    for (int i = 0; i < adj[u].size(); ++i) dfs(adj[u][i]);
}

int main() {
    cin >> n >> m;

    vis.resize(n + 1);
    adj.resize(n + 1);

    for (int i = 1; i <= m; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
    }

    return 0;
}

vis = [False] * (n + 1)
adj = [[] for _ in range(n + 1)]

for i in range(1, m + 1):
    u, v = map(int, input().split())
    adj[u].append(v)

def find_edge(u, v):
    for i in range(0, len(adj[u])):
        if adj[u][i] == v:
            return True
    return False

def dfs(u):
    if vis[u]:
        return
    vis[u] = True
    for i in range(0, len(adj[u])):
        dfs(adj[u][i])

1.3 链式前向星¶

本质上是用链表实现的邻接表，核心代码如下（边的读入顺序和存储顺序刚好相反）：

// head[u] 和 cnt 的初始值都为 -1
void add(int u, int v) {
    nxt[++cnt] = head[u]; // 当前边的后继
    head[u] = cnt;        // 起点 u 的第一条边
    to[cnt] = v;
}

// 遍历 u 的出边
for (int i = head[u]; i != -1; i = nxt[i]) {
    int v = to[i];
}

// C++ 风格
vector<int> head, nxt, to;
head.resize(n + 1, -1);

void add(int u, int v) {
    nxt.push_back(head[u]);
    head[u] = to.size();
    to.push_back(v);
}

for (int i = head[u]; i != -1; i = nxt[i]) {
    int v = to[i];
}

参考代码：

#include <iostream>
#include <vector>

using namespace std;

int n, m;
vector<bool> vis;
vector<int> head, nxt, to;

void add(int u, int v) {
    nxt.push_back(head[u]);
    head[u] = to.size();
    to.push_back(v);
}

bool find_edge(int u, int v) {
    for (int i = head[u]; i != -1; i = nxt[i]) {
        if (to[i] == v) {
            return true;
        }
    }
    return false;
}

void dfs(int u) {
    if (vis[u]) return;
    vis[u] = true;
    for (int i = head[u]; i != -1; i = nxt[i]) dfs(to[i]);
}

int main() {
    cin >> n >> m;
    vis.resize(n + 1, false);
    head.resize(n + 1, -1);
    for (int i = 1; i <= m; ++i) {
        int u, v;
        cin >> u >> v;
        add(u, v);
    }
}

边是带编号的，有时会非常有用，而且如果 cnt 的初始值为奇数，存双向边时 i^1 即是 i 的反边（常用于网络流）。

2 拓扑排序¶

在一个 DAG（有向无环图）中，我们将图中的顶点以线性方式进行排序，使得对于任何的顶点 \(u\) 到 \(v\) 的有向边 \((u, v)\)，都可以有 \(u\) 在 \(v\) 的前面。

还有给定一个 DAG，如果从 \(i\) 到 \(j\) 有边，则认为 \(j\) 依赖于 \(i\)。如果 \(i\) 到 \(j\) 有路径（\(i\) 可达 \(j\)），则称 \(j\) 间接依赖于 \(i\)。

拓扑排序的目标是将所有节点排序，使得排在前面的节点不能依赖于排在后面的节点。

2.1 AOV 网¶

日常生活中，一项大的工程可以看作是由若干个子工程组成的集合，这些子工程之间必定存在一定的先后顺序，即某些子工程必须在其他的一些子工程完成后才能开始。

我们用有向图来表现子工程之间的先后关系，子工程之间的先后关系为有向边，这种有向图称为顶点活动网络，即 AOV 网（Activity On Vertex Network）。一个 AOV 网必定是一个有向无环图。与 DAG 不同的是，AOV 的活动都表示在顶点上。

在 AOV 网中，顶点表示活动，弧表示活动间的优先关系。AOV 网中不应该出现环，这样就能够找到一个顶点序列，使得每个顶点代表的活动的前驱活动都排在该顶点的前面，这样的序列称为拓扑序列（一个 AOV 网的拓扑序列不是唯一的），由 AOV 网构造拓扑序列的过程称为拓扑排序。因此，拓扑排序也可以解释为将 AOV 网中所有活动排成一个序列，使得每个活动的前驱活动都排在该活动的前面（一个 AOV 网中的拓扑排序也不是唯一的）。

前驱活动 ：有向边起点的活动称为终点的前驱活动（只有当一个活动的前驱全部都完成后，这个活动才能进行）。
后继活动 ：有向边终点的活动称为起点的后继活动。

检测 AOV 网中是否带环的方式是构造拓扑序列，看是否包含所有顶点。

构造拓扑序列步骤¶

从图中选择一个入度为零的点。
输出该顶点，从图中删除此顶点及所有的出边。

重复上面两步，直到所有顶点都输出，拓扑排序完成，或者图中不存在入度为零的点，此时说明图是有环图，拓扑排序无法完成，陷入死锁。

2.2 关键路径和 AOE 网¶

与 AOV 网对应的是 AOE 网（Activity On Edge Network） 即边表示活动的网。AOE 网是一个带权的有向无环图，其中，顶点表示事件，弧表示活动持续的时间。通常，AOE 网可以用来估算工程的完成时间。AOE 网应该是无环的，且存在唯一入度为零的起始顶点（源点），以及唯一出度为零的完成顶点（汇点）。

AOE 网中的有些活动是可以并行进行的，所以完成整个工程的最短时间是从开始点到完成点的最长活动路径长度（这里所说的路径长度是指路径上各活动的持续时间之和，即弧的权值之和，不是路径上弧的数目）。因为一项工程需要完成所有工程内的活动，所以最长的活动路径也是关键路径，它决定工程完成的总时间。

AOE 网的相关概念¶

活动：AOE 网中，弧表示活动。弧的权值表示活动持续的时间，活动在其前驱事件（即该弧的起点）被触发后开始。
事件：AOE 网中，顶点表示事件，事件在它的所有前驱活动（即指向该边的弧）全部完成后被触发。
事件 \(v_i\) 的最早发生时间 ：该事件最早可能的发生时间，记为 \(ve(i)\)，它决定了以该顶点开始的活动的最早发生时间，显然源点的最早发生时间为 0。因为事件发生需要其所有前驱活动全部完成，所以它等于初始点到该顶点的路径长度的最大值，写成递推：\(ve(i) = \max\{ve(j) + val_i^j \mid j \in pre_i\}\)，其中 \(val_i^j\) 表示 \(j\) 到 \(i\) 的边的权值（即 \(j\) 到 \(i\) 的活动的持续时间），\(pre_i\) 表示 \(i\) 的所有前驱事件的集合。
事件 \(v_i\) 的最迟发生时间 ：在不推迟整个工期的前提下，该事件最晚能容忍的发生时间，记为 \(vl(i)\)，它决定了所有以该状态结束的活动的最迟发生时间，它等于事件的所有后继活动的最迟开始时间的最小值，即 \(vl(i) = \min\{vl(j) - val_j^i \mid j \in nxt_i\}\)，其中 \(val_j^i\) 表示 \(i\) 到 \(j\) 的边的权值，\(nxt_i\) 表示 \(i\) 的所有后继事件的集合。
活动 \((u,v)\) 的最早开始时间 ：该活动最早可能的发生时间，记为 \(e(u,v)\)，显然，它等于其前驱事件的最早发生时间，即 \(e(u,v) = ve(u)\)。
活动 \((u,v)\) 的最迟开始时间 ：在不推迟整个工期的前提下，活动开始最晚能容忍的时间，记为 \(l(u,v)\)，它等于其后继事件的最迟发生时间减去该事件的持续时间（权值），即 \(l(u,v) = vl(v) - val_v^u\)。
关键路径 ：AOE 网中从源点到汇点的最长路径的长度。
关键活动 ：即关键路径上的活动，它的最早开始时间和最迟开始时间相等。

递推求最早和最迟发生时间¶

按拓扑顺序求，最早发生时间从前往后递推，最迟发生时间从后往前递推，递推公式如上所示。

2.3 Kahn 算法¶

过程

初始状态下，集合 \(S\) 装着所有入度为 \(0\) 的点，\(L\) 是一个空列表。

每次从 \(S\) 中取出一个点 \(u\)（可以随便取）放入 \(L\)，然后将 \(u\) 的所有边 \((u, v_1), (u, v_2), (u, v_3)\dots\) 删除。对于边 \((u, v)\)，若将该边删除后点 \(v\) 的入度变为 \(0\)，则将 \(v\) 放入 \(S\) 中。

不断重复以上过程，直到集合 \(S\) 为空。检查图中是否存在任何边，如果有，那么这个图一定有环路，否则返回 \(L\)，\(L\) 中顶点的顺序就是构造拓扑序列的结果。

时间复杂度

假设这个图 \(G = (V, E)\) 在初始化入度为 \(0\) 的集合 \(S\) 的时候就要遍历整个图，并检查每一条边，因而有 \(O(E + V)\) 的复杂度。然后对该集合进行操作，显然也是需要 \(O(E + V)\) 的时间复杂度。

因而总的时间复杂度就有 \(O(E + V)\)。

int n, m;
vector<int> G[MAXN];
int in[MAXN];

bool toposort() {
    vector<int> L;
    queue<int> S;
    for (int i = 1; i <= n; i++) {
        if (in[i] == 0) S.push(i);
    }
    while (!S.empty()) {
        int u = S.front();
        S.pop();
        L.push_back(u);
        for (auto v : G[u]) {
            if (--in[v] == 0) {
                S.push(v);
            }
        }
    }
    if (L.size() == n) {
        for (auto i : L) cout << i << " ";
        return true;
    }
    else return false;
}

from collections import defaultdict, deque

def topo_sort(graph):
    lst = []
    in_degree = defaultdict(int)
    for u in graph:
        for v in graph[u]:
            in_degree[v] += 1

    s = deque([u for u in graph if in_degree[u] == 0])
    while s:
        u = s.popleft()
        lst.append(u)
        for v in graph.get(u, []):
            in_degree[v] -= 1
            if in_degree[v] == 0:
                s.append(v)

    return None if any(in_degree.values()) else lst

2.4 DFS 算法¶

using Graph = vector<vector<int>>; // 邻接表

struct TopoSort {
    enum class Status : uint8_t { to_visit, visiting, visited };

    const Graph& graph;
    const int n;
    vector<Status> status;
    vector<int> order;
    vector<int>::reverse_iterator it;

    TopoSort(const Graph& graph)
        : graph(graph),
          n(graph.size()),
          status(n, Status::to_visit),
          order(n),
          it(order.rbegin()) {}

    bool sort() {
        for (int i = 0; i < n; i++) {
            if (status[i] == Status::to_visit && !dfs(i)) return false;
        }
        return true;
    }

    bool dfs(const int u) {
        status[u] = Status::visiting;
        for (const int v : graph[u]) {
            if (status[v] == Status::visiting) return false;
            if (status[v] == Status::to_visit && !dfs(v)) return false;
        }
        status[u] = Status::visited;
        *it++ = u;
        return true;
    }
};

时间复杂度 \(O(E + V)\)，空间复杂度 \(O(V)\)。

合理性：考虑一个图，删除掉某个入度为 \(0\) 节点之后，如果新图可以拓扑排序，那么原图一定也可以。反过来，如果原图可以拓扑排序，那么删掉之后也可以。

总结¶

存储方式	空间复杂度	适用场景	特点
邻接矩阵	\(O(V^2)\)	稠密图	查询边快
邻接表	\(O(V+E)\)	稀疏图	通用
链式前向星	\(O(V+E)\)	稀疏图、网络流	支持边编号

拓扑排序算法	时间复杂度	空间复杂度	特点
Kahn 算法	\(O(V+E)\)	\(O(V)\)	BFS 思路，直观
DFS 算法	\(O(V+E)\)	\(O(V)\)	递归实现，可检测环