拓扑排序¶

引入¶

什么是拓扑排序呢？什么又是拓扑序呢？我们可以通过干活来逐渐理解。比如你现在有若干件事情要做，有些事情是可以直接做的，但是有些事情是不能直接做的，必须做完“前置任务”才可以做，而且前置任务可能还有前置任务。你需要合理安排做任务的顺序。

我们可以把这个模型放到图里面来进行理解，把每一件事看成一条有向边，比如做事情 \(i\) 之前需要做事情 \(j\)，那么就从 \(j\) 往 \(i\) 连一条有向边。有些事情可以直接做，那么这个事情对应的点的入度就是零。排出做事情的顺序的算法就叫做拓扑排序。

注意拓扑序只存在于有向无环图（DAG）当中。解释起来十分简单，因为如果有环，那么我们永远都有前置任务完成，我们就根本不知道自己需要做什么了。如果是无向图的话，那么根本就没有一件事情能够直接做，因此也没有拓扑序。

Kahn 算法¶

其实就是普通的广度优先搜索。首先，我们把入度为 \(0\) 的点全部加入进队列当中并输出，因为他们可以直接做。然后我们不断进行 bfs，每一次都取出队首的元素，然后扩散到邻点，然后邻点就少了一条入度的边。如果邻点已经没有入度了，就说明这个点的“前置任务”已经完成了，那么就把这个点加入队列并输出。

最后如果输出的元素数量达不到 \(n\)，就说明这个图当中有环。因此，拓扑排序也是一种用来检测一个有向图当中有没有环的好办法。

时间复杂度： \(\mathcal O(n+m)\)。

代码

void topo() {
  queue<int> q;
  for (int i = 1; i <= n; i++) {
    d[i] || q.emplace(i);
    d[i] || (cout << i << ' ', 0);
  }
  for (; q.size(); q.pop()) {
    for (int i : e[q.front()]) {
      if (!--d[i]) {
        cout << i << ' ';
        q.emplace(i);
      }
    }
  }
}

应用¶

除了可以判断图中有没有负环，拓扑排序还被广泛应用在图上面的 dp 中。例如以下的题目：

例题

给定一个 \(n\) 个点 \(m\) 条边的有向无环图，每一个点都有一个非负权值 \(a_i\)，要求你找出一条从 \(1\sim n\) 的最短路径，使得经过的权值之和最小。

这题可以使用我们之前学习的 Dijkstra 做，但是 \(\mathcal O(m\log_2 m)\) 的时间复杂度不够优秀，因此我们可以 dp。设 \(dp_i\) 表示为 \(1\sim i\) 经过的最小权值之和，那么任意一个 \(j\) 如果可以到达 \(i\)，那么就可以取出最小值。但是我们会发现，\(dp_j\) 不一定已经求解过，那么该怎么办呢？

其实我们只需要加入拓扑排序、并按照拓扑排序进行 dp 就可以解决这个问题。还有，如果要写收集型的话需要存反图，因此我们直接写扩散性。

提示

如果你不想写拓扑排序，那么可以存反图并使用分治解决，因为分治遍历递归求解子问题一定是已经求解过的。

代码

#include <iostream>
#include <utility>
#include <vector>
#include <queue>

using namespace std;

const int kMaxN = 1e5 + 5;

int a[kMaxN], d[kMaxN], dp[kMaxN], n, m;
vector<int> e[kMaxN], v;
queue<int> q;

void topo() {
  // 拓扑排序
  for (int i = 1; i <= n; i++) {
    // 如果入度为0，则加入队列
    if (!d[i]) {
      v.push_back(i);
      q.push(i);
    }
  }
  // 拓扑排序
  for (; q.size(); q.pop()) {
    // 遍历当前节点的所有出边
    for (int i : e[q.front()]) {
      // 如果入度减1后为0，则加入队列
      if (!--d[i]) {
        v.push_back(i);
        q.push(i);
      }
    }
  }
}

int main() {
  // 读入节点数和边数
  cin >> n >> m;
  // 读入节点1的权值
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  // 读入每条边的起点和终点，并记录入度
  for (int i = 1, u, v; i <= m; i++) {
    cin >> u >> v;
    e[u].push_back(v);
    d[v]++;
  }
  // 拓扑排序，并记录拓扑排序后的节点
  topo();
  // 初始化dp数组，dp[i]表示从节点1到节点i的最小权值和
  fill(dp + 1, dp + n + 1, 1e9);
  dp[1] = a[1];
  // 遍历拓扑排序后的节点，更新dp数组
  for (int i : v) {
    for (int j : e[i]) {
      dp[j] = min(dp[j], dp[i] + a[j]);
    }
  }
  // 输出最终结果
  cout << dp[n] << '\n';
  return 0;
}

字典序最大¶

一张图的拓扑序并不是唯一的，但是在 Special Judge 还没有出来的年代，这种输出方案的题目一般都是要使用字典序最大 / 最小的来输出。很简单，我们只需要将普通的队列改成优先队列就行了。比如一下就是输出字典序最小的拓扑序的例子：

代码

void topo() {
  priority_queue<int, vector<int>, greater<>> q;
  for (int i = 1; i <= n; i++) {
    d[i] || q.emplace(i);
    d[i] || (cout << i << ' ', 0);
  }
  while (q.size()) {
    int t = q.top();
    q.pop();
    for (int i : e[t]) {
      if (!--d[i]) {
        cout << i << ' ';
        q.emplace(i);
      }
    }
  }
}

拓扑排序¶

引入¶

Kahn 算法¶

应用¶

字典序最大¶

评论