DAG拓扑排序
引入
小学奥数类型题。
沏茶过程
(烧水壶) 到 (接水) 到 (烧水 洗茶杯 找茶叶)(并行) 到 (沏茶)
即有先后顺序的流程,且必须所有步骤都能执行。
概述
- 拓扑排序是对DAG(有向无环图)的顶点进行的一种线性排序,排序序列中每个顶点都会且仅会出现一次,且对于所有有向边 \(u\rightarrow v\),排序完后 \(u\) 都在 \(v\) 的后面。
- 如果图中存在环,就不能进行拓扑排序。
- 一个有向无环图可能有多种排序结果。
- 对于 \(n\) 个顶点的有向无环图:
- 最少存在 \(1\) 种合法的拓扑序列。
- 即该图为一条直线。
- 最多存在 \(n!\) 钟合法的拓扑序列。
- 即该图为散点,无边。
- 最少存在 \(1\) 种合法的拓扑序列。
- 对于 \(n\) 个顶点的有向无环图:
流程
- 在拓扑排序中,用 \(L\) 记录到目前为止的拓扑序列,用集合 \(S\) 记录所有不在 \(L\) 中入度为 \(0\) 的顶点。
- 步骤执行
- 首先遍历整张图上的顶点,如果一个顶点入度为 \(0\),将它加入 \(S\)。
- 当 \(S\) 不为空时:
- 在 \(S\) 中任取一个顶点 \(x\),将 \(x\) 加入到 \(L\) 的队尾,并把 \(x\) 从 \(S\) 中删去。
- 遍历从 \(x\) 出发的边 \(x\rightarrow y\),删除。如果 \(y\) 的入度变为 \(0\),则将其加入 \(S\) 中。
- 循环结束时:
- 如果所有点都加入了 \(L\),那么我们就找到了一个合法的拓扑序列。
- 如果有点不在 \(L\) 中,证明该图有环。
- \(L,S\) 用同一个队列维护。
- 时间复杂度 \(\operatorname O(n + m)\)
代码
vector<int> edge[N + 1];
int n, m, q[N + 1], d[N + 1]//q为队列,d为入度;
void topoSort()
{
int front = 1, rear = 0;
for (int i = 1; i <= n; i++)
{
if (!d[i]) q[++rear] = i;
while(front <= rear)
{
int x = q[front];
++front;
for (auto to : edge[x])
{
if (--d[to] == 0)//没必要真的删边,维护d数组即可
{
q[++rear] = to;
}
}
}
}
if (rear == n)
{
printf("合法");
}
else
{
printf("不合法");
}
}