拓扑排序——思想、例题及C++实现（更新中）

一、何为拓扑排序

1.1 有向无环图 DAG

1.2 如何判断 DAG

1.3 拓扑排序

二、拓扑排序的方法

2.1 遍历法

2.2 删除入度为0结点法

三、例题详解

3.1 课程表

3.2 课程表2

一、何为拓扑排序

1.1 有向无环图（DAG）
一张图若为有向无环图（DAG, Directed Acyclic Graph），则必须满足：

该图为有向图，且每个顶点只出现一次。
图中没有环的存在

一张DAG图可以有很多种表示方式，如链表表示（用指针存储后继），数组表示（用数组表示后继）等。故DAG题目多变，但解法与思想都是一样的。

1.2 如何判断DAG
对于图的遍历过程而言，若在遍历A元素的所有后继（包括后继的后继...）的时候，再次遍历到了A，说明图中存在环，非DAG。

对于删除入度为0的元素的过程而言，若某一时刻不存在入度为0的元素，但依然图中有元素存在，说明图中存在环，非DAG。（“入度”：指向该结点的边的条数）

1.3 拓扑排序
拓扑排序就是遍历一张DAG图，得出遍历元素的先后顺序的过程。若把图中所有顶点视为“事件”，把有向边视为“先后顺序”，则可以将DAG图视为一个表示各事件发生先后顺序的“AOV 网” 。而对DAG进行拓扑排序，就是要找出一个合理的做事情的顺序。与拓扑排序有关的题，基本都是这个类型。

二、拓扑排序的方法

2.1 遍历法
遍历法的基本思想是：若在遍历A元素的所有后继（包括后继的后继...）的时候，再次遍历到了A，说明图中存在环，非DAG。

具体怎么实现呢？我们可以设置一个 visited 数组，用来表示每个结点的搜索状态，搜索状态有三种——0：未搜索、1：正在搜索其全部后继、2：搜索完成。采用深度优先的递归遍历的方式：

将visited初始值全部设为0
准备搜索A，检查visited[A]：
若visited[A] == 1，说明A已处于搜索状态：A发起的搜索重新搜索到了A，图中存在环，非DAG图，结束拓扑排序。
若visited[A] == 2，说明A及其全部后继已被搜索，不再做任何处理。
若visited[A] == 0，将visited[A]置为1，并递归搜索A的全部后继。
若在递归搜索的某时刻，发现visited 为 1，说明出现了环，结束拓扑排序
若所有元素都成功完成搜索，说明这是一张DAG，拓扑排序的结果就是搜索元素的顺序

例题：见第三节——3.1 课程表、3.2 课程表2

2.2 删除入度为0结点法
待更新

三、例题详解

3.1 课程表

题目：

        你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

        在选修某些课程之前需要一些先修课程。先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则必须先学习课程  bi 。

        例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
        请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

        （题目来源：LeetCode https://leetcode.cn/problems/course-schedule/）

思路：（遍历法）

        采用DFS进行遍历，用一个栈来存储所有已经搜索完成的节点。

        对于一个节点 u，当它的所有直接后继都已经搜索完成（入栈），那么 u 便搜索完成。

        假设我们当前搜索到了节点 u，如果它的所有相邻节点都已经搜索完成，那么这些节点都已经在栈中了，此时我们把 u 入栈。此时，我们从栈顶向下看，由于 u 处于栈顶的位置，u 的所有直接后继都在 u 的下方，且每一次更新栈都满足这个规律。说明栈就是拓扑排序的结果。

算法：

        对于图中的任意一个节点，它在搜索的过程中有三种状态，即：

「未搜索」：我们还没有搜索到这个节点；
「搜索中」：我们搜索过这个节点，但其后继还没有搜索完成（没有入栈），该元素也没有入栈
「已完成」：该元素的所有后继都已搜索完成（入栈），该元素也已入栈。

        在每一轮的搜索搜索开始时，我们任取一个「未搜索」的节点开始进行深度优先搜索。

        我们将当前搜索的节点 u 标记为「搜索中」，遍历该节点的每一个相邻节点 v：

如果 v 为「未搜索」，那么我们开始搜索 v，待搜索完成回溯到 u；
如果 v 为「搜索中」，那么我们就找到了图中的一个环，结束拓扑排序；
如果 v 为「已完成」，直接返回。

当 u 的所有相邻节点都为「已完成」时，我们将 uu 放入栈中，并将其标记为「已完成」。

在整个深度优先搜索的过程结束后，如果我们没有找到图中的环，那么栈中存储这所有的 nn 个节点，从栈顶到栈底的顺序即为一种拓扑排序。

作者：LeetCode-Solution
链接：力扣
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

#include 
#include 
using namespace std;

vector> edges;  // edges[i]存储元素i的直接后继
vector visited;        // 0未搜索，1搜索中，2搜索完成
bool valid = true;          // DAG判断标志

void dfs(int u) {
    // 搜索开始，将visited置1
    visited[u] = 1;
    // 递归搜索u的所有后继
    for (int v: edges[u]) {
        if (visited[v] == 0) {
            dfs(v);
            if (!valid)
                return;
        }
        // 出现了环
        else if (visited[v] == 1) {
            valid = false;
            return;
        }
    }
    visited[u] = 2;
}
bool canFinish(int numCourses, vector>& prerequisites) {
    edges.resize(numCourses);
    visited.resize(numCourses, 0);
    // 将 1->2, 1->3 整合为 edges[1] = {2,3}
    for (const auto& info: prerequisites)
        edges[info[1]].push_back(info[0]);
    // dfs
    for (int i = 0; i < numCourses && valid; ++i)
        if (!visited[i])
            dfs(i);

    return valid;
}
int main() {
    int numCourses = 10;
    vector> prerequisites = {{5,8},{8,5},{1,9},{4,5},{0,2},{7,8},{4,9}};
    bool flag = canFinish(numCourses, prerequisites);
    if (flag)
        cout << "Topologic sort success, there are no rings." ;
    else    
        cout << "Topologic sort fail, there are rings." ;

    return 0;
}

3.2 课程表2

题目：

        现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前必须先选修 bi 。

        例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。
返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回任意一种就可以了。如果不可能完成所有课程，返回一个空数组。

（题目来源：https://leetcode.cn/problems/course-schedule-ii/）

思路：
整体思路与 3.1 课程表相同。但要按序输出事件，则必须从入度为 0 的结点开始遍历。不过，图中可能存在这样一种情况：有一部分是非环，有一部分是环且不存在入度为0的点，因为不会对这样的环进入搜索，只用 DAGflag 无法判断，所以在最后还要用 ans.size() 判断一次。

#include 
#include 
using namespace std;

vector ans;                    // 结果
vector> subsequence;    // 后继结点
vector visited;                // 访问状态
vector in_degree;              // 入度
bool DAGflag = true;                // DAG标志

void dfs(int i) {
    // 在其他搜索中发现环，返回
    if (!DAGflag)
        return;
    // 已完成搜索，返回
    if (visited[i] == 2)
        return;
    // 还处于搜索状态，说明发现了环
    if (visited[i] == 1) {
        DAGflag = false;
        return;
    }
    // 还未搜索过
    visited[i] = 1;
    for (int s : subsequence[i])
        if (DAGflag)
            dfs(s); 
    ans.push_back(i);
    visited[i] = 2;
}
vector findOrder(int numCourses, vector>& prerequisites) {
    subsequence.resize(numCourses);
    visited.resize(numCourses, 0);
    in_degree.resize(numCourses, 0);
    
    for (const auto& p : prerequisites) {
        // 计算每个结点的入度
        in_degree[p[1]]++;
        // 合并每个结点的后继结点到 subsequence
        subsequence[p[0]].push_back(p[1]);
    }
    // 遍历所有入度为0的结点
    for (int i = 0; i < numCourses && DAGflag; i++)
        if (in_degree[i] == 0)
            dfs(i);
    // 若非DAG图，将ans清空
    if (!DAGflag || ans.size() != numCourses)
        ans.clear();

    return ans;
}
int main() {
    int numCourses = 4;
    vector> prerequisites = {{1,0},{2,0},{3,1},{3,2}};
    vector res = findOrder(numCourses, prerequisites);

    if (DAGflag && res.size() == numCourses) {
        cout << "Topologic sort success, there are no rings." << endl;
        for (int i : res) 
            cout << i << " ";
    } else
        cout << "Topologic sort fail, there are rings." ;

    return 0;
}

拓扑排序——思想、例题及C++实现（更新中）

一、何为拓扑排序

二、拓扑排序的方法

2.2 删除入度为0结点法 待更新

三、例题详解

Java相关栏目本月热门文章

2.2 删除入度为0结点法
待更新