33DAI：批量导入三三文档

2026-05-20T18:24:07Z

批量导入三三文档

←上一版本		2026年5月20日 (三) 18:24的版本
第82行：		第82行：
	[[Category:图论]]		[[Category:图论]]
	[[Category:三三文档]]		[[Category:三三文档]]

33DAI：导入1个版本

2026-05-20T18:12:24Z

导入1个版本

←上一版本	2026年5月20日 (三) 18:12的版本
（没有差异）

->Importer：批量导入三三文档

2026-05-20T16:50:33Z

批量导入三三文档

新页面

== 拓扑排序 ==

拓扑排序只适用于'''有向无环图（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:三三文档]]

11-图论/04-拓扑排序 - 版本历史

33DAI：​批量导入三三文档

33DAI：​导入1个版本

->Importer：​批量导入三三文档

33DAI：批量导入三三文档

33DAI：导入1个版本

->Importer：批量导入三三文档