查看“︁11-图论/04-拓扑排序”︁的源代码


== 拓扑排序 ==

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

=== 应用场景 ===

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

=== BFS 实现（Kahn 算法） ===

每次选入度为 <math>0</math> 的点输出并删除：

<syntaxhighlight lang="cpp">
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;
}
</syntaxhighlight>

=== DFS 实现 ===

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

<syntaxhighlight lang="cpp">
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()); // 逆序即为拓扑序
</syntaxhighlight>

[[Category:图论]]
[[Category:三三文档]]