拓扑排序

概述

对一个 $DAG$ (有向无环图) $G$ 进行拓扑排序，是将 $G$ 中所有顶点排成一个线性序列，使得图中任意一对顶点 $u$ 和 $v$ ，如果存在一条有向边 $u->v$ 则 $u$ 在 $v$ 之前出现。简单来说，是在不破坏节点先后顺序的情况下，把 $DAG$ 拉成一条链。

注意：拓扑排序可能不是唯一的。

Kahn算法

首先获取所有**入度为 $0$ **的节点，将他们排在前面然后从图中删除。此时有些点的入度会减少，重复前面的操作直到所有点都被删除(输出)。

我们可以通过 $BFS$ 来实现，使用一个队列，首先遍历入度为0的节点(这些节点入队)，队首出队，与队首所连节点度数 $-1$ ，如果有节点度数减为0将其加入队列，重复上述操作直至队列为空。

示例代码

struct edge
{	int to;//指向的节点
 	int NextE;//下一条边
} e[100];
int num_e = 0;//边数
int head[100];//节点
int num_D[100];//节点度数
vector<int> ToPu(int n)
{
    vector<int> a;
    int cnt = 0;
    queue<int> q;
    for (int i = 1; i <= n; i++)
    {
        if (num_D[i] == 0) // 入度为0
        {
            q.push(i); // 入队
        }
    }
    while (!q.empty())
    {
        int x = q.front(); // 获取队首
        q.pop();           // 出队
        a.push_back(x);
        for (int i = head[x]; i; i = e[x].NextE)
        {
            num_D[e[i].to]--;        // x指向的节点度数减一
            if (num_D[e[i].to] == 0) // 度数为0
            {
                q.push(e[i].to); // 入队
            }
        }
    }
    return a;
}

基于DFS

我们可以在 $DFS$ 的过程中使用一个栈来记录访问的顺序，由定义可知位于最"深"层的节点经过拓扑排序后会在最后输出，而 $DFS$ 是直到最"深"层的节点才开始递归。所以我们可以在将该节点先存入栈中，最后再输出。

即当某节点的所有子节点都入栈后，才将该节点入栈。

示例代码

void DFS(int i, vector<bool> &vis, stack<int> &a)
{
    vis[i] = true;

    for (int j = head[i]; j; j = e[i].NextE)
    {
        if (!vis[e[j].to])
        {
            DFS(e[j].to, vis, a);
        }
    }

    //i顶点下所有子顶点都入栈，i才入栈
    a.push(i);
}
stack<int> ToPuDFS(int n)
{
    stack<int> a;
    vector<bool> vis(n + 1, false);

    for (int i = 1; i <= n; i++)
    {
        if (!vis[i])
            DFS(i, vis, a);
    }

    // 输出
    while (!a.empty())
    {
        cout << a.top() << " ";
        a.pop();
    }
}