图（二）

拓扑排序

拓扑排序不是一般意义上的“排序”。

引入：

例 1：

对于一个家族，给出每个人的孩子的序号，输出一个序列，使得每个人的祖先都比他先列出。

将每个人视作图中的一个节点，若 $v$ 是 $u$ 的孩子，则视作边 $(u,v)$，那么形成的图一定是一个有向无环图，拓扑排序就是针对有向无环图的算法。

第一个输出的点一定是不存在祖先的节点，体现在图上即：入度为 $0$ 的节点。每输出一个点，就在图上取下这个点。当一个节点的祖先全部输出后，这个点便可以被输出，因为满足了它的祖先都比它先输出了。

通常使用队列模拟上述过程，此算法被称为 Kahn 算法。通常来说，拓扑排序均指 Kahn 算法。（使用队列模拟即 BFS 实现，也可以使用 DFS 实现，但通常不这么做）

For(i,1,n) if(!in[i]) q.push(i);
while(q.size()){
	auto now=q.front();
	seq.push_back(now);
	q.pop();
	for(auto u:p[now]){
		in[u]--;
		if(!in[u]) q.push(u);
	}
}

时间复杂度：$O(|V|+|E|)$。

拓扑排序实现 DP：

回顾记忆化搜索中提到的子结构，其维护的是从当前状态到终点的信息，而扫表对应的是从起点到当前状态的信息，拓扑排序同样维护的是起点到当前状态的信息。

其一，考虑搜索树，容易发现，若为树上的边赋予一个“方向”，那么树就是一个有向无环图。所以记忆化搜索的状态之间即为一个有向无环图，这便满足了可以进行拓扑排序的前置条件。

其二、对于扫表而言，其保证了用一个状态的值去转移另一个状态时，它的值是正确（不会再被转移）所以，对应到图上，也就是没有入度了。同样是一个有向无环图。

例 2：

给定一个食物网，用 $(u,v)$ 描述 $u$ 吃 $v$，求食物网中存在多少条最大食物链，最大食物链即最左端不存在吃的，最右端不存在被吃的。

状态：

设 dp$[x]$ 表示以 x 为最右端的最大食物链数。

转移：

$(v)\leftarrow(u)$

此时，枚举的顺序就不容易确定了，因为要保证用于转移的状态是正确的，所以并不能直接从小到大枚举生物。此时就可以用拓扑排序实现。

DP 式子：

For(i,1,n) if(!in[i]) q.push(i),dp[i]=1;
while(q.size()){
    auto now=q.front();
    q.pop();
    for(auto u:p[now]){
        dp[u]+=dp[now];
        in[u]--;
        if(!in[u])
            q.push(u);
    }
}

拓扑排序判环：

有向图中判环拓扑排序的一个简单小应用。

（理论上有环不是有向无环图，那自然算不得拓扑排序，所以其实叫 Kahn 判环会更合适）

对于一个环，其没有入度为 $0$ 的点，也就无法进入循环，同时无法去掉环上的点。

所以跑一遍拓扑排序后，入度不为 $0$ 的点就是在环上的点。

番外：

记忆化搜索、扫表、拓扑排序的对比：

记忆化搜索：

维护的是从当前状态到终点的信息。

优点：

在处理容易视作“子结构”的问题中，会更好理解。

因为其“子结构”性质，不会访问到无用状态。

缺点：

需要记录所有用到的状态，不能滚动数组优化空间，且不容易使用数据结构优化时间。

扫表：

维护的是从起点到当前状态的信息。

优点：

在处理小规模到大规模明确的问题中更好写。

相比记忆化搜索不用记录状态，所以在部分情况下可以使用滚动数组优化空间，可以使用数据结构优化时间。

缺点：

需要枚举所有状态，会遇到无用的状态。

在枚举顺序不容易确定的情况，比较难写（转移关系顺序难确定）。

拓扑排序：

维护的是从起点到当前状态的信息。

优点：

处理图论模型，不用考虑枚举顺序，在有向无环图上“自动”解决枚举顺序。在状态之间关系明确的情况下容易建图实现。

和扫表同样可以滚动数组优化空间和数据结构优化空间（因为本质是 BFS，可以预处理深度后按层处理）

同时不需要枚举所有状态空间，也能避免遇到无用的状态。

缺点：

需要建图。

代码相对复杂。