相关概念：

• 拓扑排序，就是在有向图中找到一条拓扑序列，序列中排列在前的节点相较于排列在后的节点有更高的优先级。

  • 首先要理解优先级，优先级是有向图中边的方向性带来的结果，如 a -> b 表示节点 a 指向节点 b，则可以认为 a 的优先级优于 b，在特定语境下可以说 a 必须在 b 之前完成，如下图所示，该有向图的拓扑排序结果为 14325 或 41325。

  • 拓扑排序算法可以用来判断有向图是否有环，可以生成拓扑序列。

    • 网络中可能存在多个拓扑排序结果。
    • 如果网络中不存在环，则结果中会包括所有节点。
    • 但如果网络中存在环，则结果中可能会缺少某些节点。
• 图可以有不同的表现形式，如邻接矩阵表示形式和邻接表表示形式，有向图的邻接表表示形式。
  • 简单来说，假设图中有 m 个节点，邻接表就是维护一个 m 大小的数组 vec，其中数组元素为当前节点的外接节点链表。【例如在网络中 a -> b 且 a -> c，则数组中 a 节点对应的位置就保存一个链表 b => c，相当于 vec(a) => b => c （此处用 => 表示链表指针，b 和 c 在链表中的顺序不分先后）】
  • 也就是说，数组中第 i 个元素（记住数组元素为链表）保存的是网络中第 i 个节点的 one-hop neighbor。【即节点跳一步就可以达到的邻居节点】
• 进行后续算法的介绍前，还需要理解节点的入度。
  • 当前节点的入度，指的就是网络中有多少节点直接指向当前节点。【如上图所示，节点 3 的入度为 2 】
  • 可用一个数组统计每个节点的入度。

核心思路：

• 拓扑排序问题有两种解决方案：Kahn 算法和 dfs 着色解法。

• Kahn 算法的核心思想就是每次删除一个当前入度为 0 的节点，并删除该节点对链出邻居的影响（即其指向邻居的入度数减一）。

  • Kahn 算法需要图的邻接表形式。
  • 可以用 stack 或 queue 来保存当前入度为 0 的节点。【即用 stack 或 queue 维护当前入度为 0 的点集】
  • 用上面的图来理解，Kahn 算法的第一步就是把节点 1 带来的影响消去，留下其余的节点和边作为子图进行拓扑排序：

• dfs 着色解法即利用深度优先算法的方法以任意顺序遍历图中所有节点，但遍历的过程中需要对节点着色。

  • 不同的颜色代表访问的程度深浅，过程中遇到不同颜色的节点会有相应的处理；需要一个数组维护网络中节点的颜色，颜色的状态可以为 0、-1 和 1。
    • -1 表示访问过，如果重复遇上，则说明存在环。
  • 最后需要把结果数组进行 reverse 操作，得出来的才是拓扑序列。【因为 dfs 着色解法会优先深度搜索到优先级最低的节点，所以最先存入结果数组的就是优先级最低的节点，最后结果数组就需要翻转过来才可】

算法步骤：

• Kahn 算法的算法步骤如下：【假设用栈来维护点集】

  1. 初始化，所有入度为 0 的节点入栈。
  2. 每次从栈中 pop 出一个节点放入结果数组。
     1. 同时该节点指向的所有节点都需要进行入度减一操作。
     2. 如果邻居的入度变为 0 则邻居入栈。
  3. 不断重复 2 过程直到栈为空。
  4. 如果结果数组个数为网络中节点个数，则说明网络中无环，否则说明网络中有环。

• dfs 着色解法的算法步骤如下：

  1. 初始化，所有点染色为 0。
  2. 遍历每个节点进入 dfs 函数。【如果要遍历的点颜色不为 0，则不进入递归】
     1. 假设当前节点为 x，将其染色为 -1，接着遍历 x 的邻居。
     2. 假若当前邻居 y 的颜色为 0 ，则递归进入 dfs(y)；假若当前邻居 y 的颜色为 -1，则说明网络中存在环。
     3. 假若当前节点 x 的所有邻居都走完且没有发现环，则把 x 保存进结果数组中。
  3. 将结果数组进行翻转操作。

实现代码：

• Kahn 算法的实现代码如下：

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

vector<int> kahn_algorithm(vector<vector<int>> &graph, vector<int> &in, int n) {
    
  vector<int> ans;
  stack<int> stk;

  // 第一步，初始化
  for (int i = 1; i <= n; ++i)
    if (in[i] == 0)
      stk.push(i);
  
  // 第二步，从栈中一直 pop 出元素并存放到结果中
  while (!stk.empty()) {
    
    int x = stk.top();
    stk.pop();
    ans.push_back(x);
    for (auto &next : graph[x])
      if (--in[next] == 0)
        stk.push(next);
  }
  return ans;
}

int main() {
    
  int m, n; // 输入 m 条边，n 个节点，节点标记为 1~n
  cin >> m >> n;
  vector<int> in(n + 1);            // 入度数组
  vector<vector<int>> graph(n + 1); // 邻接表
  for (int i = 0; i < m; ++i)       // 输入 m 的边的具体情况
  {
    
    int a, b;
    cin >> a >> b;
    ++in[b];
    graph[a].push_back(b);
  }
  vector<int> ans = kahn_algorithm(graph, in, n);
  for (int num : ans)
    cout << num << " ";
  cout << endl;
  return 0;
}

• dfs 着色解法的实现代码如下：

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

vector<int> ans;

bool dfs(vector<vector<int>>& graph, vector<int>& color, int x)
{
    
  color[x] = -1;
  for(int y : graph[x])
  {
    
    if(color[y] == -1 or (color[y] == 0 and dfs(graph, color, y) == false)) // 有环
      return false;
  }
  color[x] = 1;
  ans.push_back(x);
  return true;
}

bool dfs_color(vector<vector<int>> &graph, int n)
{
    
  vector<int> color(n+1, 0);
  for(int x = 1; x <= n; ++x) if(color[x] == 0)
  {
    
    if(dfs(graph, color, x) == false) return false;
  }
  reverse(ans.begin(), ans.end());
  return true;
}

int main() {
    
  int m, n; // 输入 m 条边，n 个节点，节点标记为 1~n
  cin >> m >> n;
  vector<vector<int>> graph(n + 1); // 邻接表
  for (int i = 0; i < m; ++i)       // 输入 m 条边的具体情况
  {
    
    int a, b;
    cin >> a >> b;
    graph[a].push_back(b);
  }

  if(dfs_color(graph, n) == false)
  {
    
    cout << "有环" << endl;
    return 0;
  }

  for (int num : ans)
    cout << num << " ";
  cout << endl;
  return 0;
}

部分题目：

• leetcode - 剑指 Offer Ⅱ 115.重建序列