欢迎访问我的博客:blog.chungzh.cn

引入

给定一张有向无环图(DAG, Directed Acyclic Graph),对其顶点进行排序,使得对于每条从 uuvv 的有向边 (u,v)(u, v)uu 在排序中都在 vv 的前面。这种排序就称为拓扑排序(Topological sorting)。

当且仅当图中没有定向环时(即有向无环图),才有可能进行拓扑排序。如果排序失败,就说明该有向图存在环,不是 DAG。

任何有向无环图至少有一个拓扑排序。

举例:在某校的选课系统中,存在这样的规则:每门课可能有若干门先修课,如果要修读某一门课,则必须要先修读此课程所要求的先修课后才能修读。假设一个学生同时只能修读一门课程,那么,被选课系统允许的他修完他需要所有课程的顺序是一个拓扑序。

在这个例子中,每一门课程对应有向图中的一个顶点,每一个先修关系对应一条有向边(从先修课指向需要先修课的课)。

算法

Kahn 算法

初始状态下,集合 SS 装着所有入度为 00 的点,LL 是一个空列表。

每次从 SS 中任意取出一个点 uu 放入 LL, 然后将 uu 的所有边 (u,v1),(u,v2),(u,v3)(u, v_1), (u, v_2), (u, v_3) \cdots 删除。对于边 (u,v)(u, v),若将该边删除后点 vv 的入度变为 00,则将 vv 放入 SS 中。

不断重复以上过程,直到集合 SS 为空。检查图中是否存在任何边,如果有,那么这个图一定有环路,否则返回 LLLL 中顶点的顺序就是拓扑排序的结果。

基本上就是 BFS 的框架。

代码实现

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;
  }
}

DFS 算法

借助 DFS 完成拓扑排序:在访问完一个结点之后把它加到当前拓扑序的首部

代码实现

c[u] == 0 时,表示从来没有被访问过(从来没有调用过 dfs(u));c[u] == 1 时,表示已经访问过,而且还递归访问过它的所有子孙(即调用过 dfs(u) 且已返回);c[u] == -1 时表示正在访问(即递归调用 dfs(u) 正在栈帧中,尚未返回)。

int n, m;
vector<int> G[MAXN];
int c[MAXN], topo[MAXN], t;
bool dfs(int u) {
  c[u] = -1;
  for (auto v : G[u]) {
    if (c[v] < 0)
      return false;
    else if (c[v] == 0 && !dfs(v))
      return false;
  }
  c[u] = 1;
  topo[--t] = u;
  return true;
}
bool toposort() {
  t = n;
  memset(c, 0, sizeof(c));
  for (int i = 1; i <= n; i++)
    if (!c[i])
      if (!dfs(i)) return false;
  return true;
}

练习

参考资料