拓扑排序问题

拓扑排序的英文是Topological sorting，要解决的问题是，给定一个包含\(n\)个节点的有向图\(G\)，给出所有节点的一种排列，使得对于图\(G\)中的任意一条有向边\((u,v)\)，\(u\)在排列中都出现在\(v\)的前面，这样的排列称为图\(G\)的拓扑排序。从拓扑排序的定义中，可以得出两个结论：

1. 若图\(G\)中存在环（不是有向无环图），则图\(G\)不存在拓扑排序。
2. 若图\(G\)存在拓扑排序，则它的拓扑排序可能不止一种。一个最极端的梨子就是图\(G\)中的所有点之间不存在任何边相连，则任意一种排序都可以作为该图对应的拓扑排序。

拓扑排序最常用也是最现实的一个例子就是大学的课程计划，我们知道大学课程存在先修课的概念，学生要想学习课程\(v\)，必须要先通过课程\((u_1, u_2, \dots, u_n)\)的考试。将这个问题建模成一个拓扑排序的问题，我们可以把每一门课建模成图中一个节点，两门课程的先修关系建模成一条有向边。图片摘自OI Wiki。

力扣题目链接

方法一：广度优先搜索，Kahn算法

在一个合法拓扑排序中，最前面的节点的入度一定为0，我们首先搜索所有入度为0的节点，在遍历之后将这些节点和所有出边从图中移除。经过这一步之后如果有节点变成入度为0，说明这门课程的先修课程已经学完，可以开始学习了。我们不断将入度为0的节点加入排列中，最终可以得到一个合法的拓扑排序。如果结束后图中仍存在节点，说明这些节点入度无法变成0，图中存在环，因此也不存在拓扑排序。

vector<vector<int>> edges;  // 图
vector<int> indeg;  // 每个节点的入度
vector<int> result;  // 拓扑排序

vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
    edges.resize(numCourses);
    indeg.resize(numCourses);
    for (const auto& info : prerequisites) {
        edges[info[1]].push_back(info[0]);  // 构造图
        ++indeg[info[0]];  // 构造入度为0的节点集合
    }

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

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        result.push_back(u);
        for (int v : edges[u]) {
            --indeg[v];  // 移除节点u的出边，将节点v的入度减一
            if (indeg[v] == 0) {
                q.push(v);
            }
        }
    }

    if (result.size() != numCourses) {
        return {};  // 不存在拓扑排序
    }
    return result;
}

方法二：深度优先搜索

使用一个栈进行深度优先搜索。对于一个节点\(u\)，如果我们将它的相邻节点（即从自身开始经过一步搜索可以到达的所有节点）全部搜索完成，当搜索回溯到它自身时，其本身也成为了一个搜索完成的节点，此时它全部相邻节点已经入栈，我们再将其自身入栈，那么从栈顶往栈底看，节点\(u\)就出现在所有相邻节点的上方（拓扑排序序列的前方）。那么此时这个栈中保存的序列对于\(u\)而言是满足拓扑排序的要求的。

这样以来，我们对图进行一遍深度优先搜索。当每个节点进行回溯的时候，我们把该节点放入栈中。最终从栈顶到栈底的序列就是一种拓扑排序。

对于图中任意一个节点，它会处于三种状态：

1. 未搜索。
2. 搜索中，我们已经搜索到这个节点，但还没有回溯到它这里，即它还没有入栈，我们此时正在搜索它的相邻节点。
3. 已完成。我们已经回溯过这个节点，即它已经入栈，且它的所有相邻节点都处于栈更底部的位置，满足拓扑排序的要求。

在每一次dfs开始时，我们任取一个“未搜索”的节点进行搜索。

1. 将该节点\(u\)标记为“搜索中”，遍历它的所有相邻节点\(v\)：
   1. 如果\(v\)是“未搜索”的，那么开始搜索\(v\)，搜索完成之后回溯到\(u\)。
   2. 如果\(v\)是“搜索中”的，说明我们找到了一个环，不存在拓扑排序。
   3. 如果\(v\)是“已完成”的，说明\(v\)已经在栈中，不需要进行任何操作。
2. 所有相邻节点\(v\)都已经完成搜索，即“已完成”，我们将\(u\)入栈。

如果dfs完成之后，没有发现任何环，那么此时栈中的序列中栈顶到栈底就是一个合法的拓扑排序。

vector<vector<int>> edges;  // 图
vector<int> visited;  // 记录每个节点的状态，0=未搜索，1=搜索中，2=已完成
vector<int> result;  // 拓扑排序
bool valid{true};  // 图中是否有环存在

void dfs(int u) {
    visited[u] = 1;  // 标记当前节点u搜索中
    for (int v : edges[u]) {
        if (visited[v] == 0) {  // 如果相邻节点v未搜索
            dfs(v);
            if (!valid) {
                return;
            }
        } else if (visited[v] == 1) {  // 如果相邻节点v搜索中，说明存在环
            valid = false;
            return;
        }
    }
    visited[u] = 2;  // 回溯完成，标记当前节点u已完成
    result.push_back(u);
}

vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
    edges.resize(numCourses);
    visited.resize(numCourses);
    for (const auto& info: prerequisites) {
        edges[info[1]].push_back(info[0]);
    }
    for (int i = 0; i < numCourses && valid; ++i) {
        if (!visited[i]) {  // 每次选一个未搜索的节点进行dfs
            dfs(i);
        }
    }
    if (!valid) {  // 如果存在环，说明不存在拓扑排序
        return {};
    }
    reverse(result.begin(), result.end());
    return result;
}