拓扑排序

「拓扑排序」针对的「图」的类型必须同时满足以下条件：

• 有向无环图；
• 「图」中至少有一个顶点「入度」为 0 。如果「图」中所有顶点都有「入度」，则代表所有顶点都至少有一个前置顶点，那么这个就没有顶点可以作为「拓扑排序」的起点。

我们一般使用 Kahn 算法来解决这个问题

Kahn 算法 (广度优先搜索)

算法

我们使用一个队列来进行广度优先搜索。开始时，所有入度为 0 的节点都被放入队列中，它们就是可以作为拓扑排序最前面的节点，并且它们之间的相对顺序是无关紧要的。

在广度优先搜索的每一步中，我们取出队首的节点 $u$：

• 我们将 $u$ 放入答案中；

• 我们移除 $u$ 的所有出边，也就是将 $u$ 的所有相邻节点的入度减少 1。如果某个相邻节点 $v$ 的入度变为 0，那么我们就将 $v$ 放入队列中。

在广度优先搜索的过程结束后。如果答案中包含了这 $n$ 个节点，那么我们就找到了一种拓扑排序，否则说明图中存在环，也就不存在拓扑排序了。

实现

C++

class Solution {
 public:
  vector<int> topoSort(int num, vector<vector<int>>& graph) {
    // num 代表顶点的数量
    // 存储有向图
    vector<vector<int>> edges(num);
    // 存储每个节点的入度
    vector<int> indeg(num);
    // 存储答案
    vector<int> ans;

    for (const auto& e : graph) {
      edges[e[1]].push_back(e[0]);
      ++indeg[e[0]];
    }

    queue<int> q;
    // 将所有入度为 0 的节点放入队列中
    for (int i = 0; i < num; ++i) {
      if (indeg[i] == 0) {
        q.push(i);
      }
    }

    while (!q.empty()) {
      // 从队首取出一个节点
      int u = q.front(); q.pop();
      // 放入答案中
      ans.push_back(u);
      for (int v : edges[u]) {
        --indeg[v];
        // 如果相邻节点 v 的入度为 0，就可以选 v 对应的课程了
        if (indeg[v] == 0) {
          q.push(v);
        }
      }
    }

    if (ans.size() != num) {
      return {};
    }
    return ans;
  }
};

Python

def topoSort(graph, indeg):
    topo = []
    queue = []

    for i in range(len(indeg)):
        if indeg[i] == 0:
            queue.append(i)

    while queue:
        node = queue.pop(0)
        topo.append(node)
        for i in range(len(graph[node])):
            v = graph[node][i]
            indeg[v] -= 1
            if indeg[v] == 0:
                queue.append(v)

    if len(topo) == len(indeg):
        print(topo)
        return True
    return False

深度优先搜索

DFS 的思路非常直观， 我们对图进行 DFS 遍历，每到一个结点就将其插入返回数组， 完成遍历后反转数组即可。

算法

vector<vector<int>> edge;  // vector 实现的邻接表
vector<int> vis;           // 标志数组
vector<int> topo;          // 拓扑排序后的节点

bool dfs(int u) {
  vis[u] = -1;
  for (int v : edge[u]) {
    if (vis[v] < 0) {
      return false;  // 有环
    } else if (!vis[v] && !dfs(v) {
      return false;
    }
  }
  vis[u] = 1;
  topo.push_back(u);
  return true;
}

bool topoSort() {
  topo.clear();
  vis.resize(n, 0);
  for (int u = 0; u < n; u++) {
    if (!vis[u] && !dfs(u)) {
      return false;
    }
  }
  reverse(topo.begin(), topo.end());
  return true;
}

例题

LC207.课程表

LC210.课程表 II

LC851.喧闹和富有