11-图论/04-拓扑排序

拓扑排序

拓扑排序只适用于有向无环图（DAG），将顶点排序成线性序列，使得每条边 [math]\displaystyle{ u \to v }[/math] 中 [math]\displaystyle{ u }[/math] 排在 [math]\displaystyle{ v }[/math] 前面。

应用场景

• 课程先修关系（A 是 B 的先修课）
• 编译依赖顺序
• 任务调度

BFS 实现（Kahn 算法）

每次选入度为 [math]\displaystyle{ 0 }[/math] 的点输出并删除：

vector<int> g[MAXN];
int indeg[MAXN]; // 入度

vector<int> topo_sort(int n)
{
    vector<int> res;
    queue<int> q;

    for (int i = 1; i <= n; i++)
        if (indeg[i] == 0)
            q.push(i);

    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        res.push_back(u);

        for (int v : g[u])
        {
            indeg[v]--;
            if (indeg[v] == 0)
                q.push(v);
        }
    }

    // 若 res.size() < n，说明图中有环
    return res;
}

DFS 实现

后序遍历的逆序即为拓扑序：

vector<int> g[MAXN];
bool vis[MAXN], on_path[MAXN];
vector<int> topo;

bool dfs(int u)
{
    vis[u] = true;
    on_path[u] = true;
    for (int v : g[u])
    {
        if (!vis[v])
        {
            if (!dfs(v)) return false;
        }
        else if (on_path[v])
            return false; // 有环
    }
    on_path[u] = false;
    topo.push_back(u);
    return true;
}

// 调用
for (int i = 1; i <= n; i++)
    if (!vis[i])
        dfs(i);
reverse(topo.begin(), topo.end()); // 逆序即为拓扑序