拓扑排序并不一定唯一，有时会要求顶点数值大的尽量在前，这个时候应该反向建图，再进行拓扑排序，来保证更多小数值顶点在后面。（贪心思想？）
Eg：HDU 4857 POJ 3687（反向建图+拓扑排序）
5.优化
拓扑排序每次选择一个顶点进入序列后，要更新所有与这个顶点相连的顶点的入度。而上面的代码全是把所有的顶点都遍历了一边。
这里可以使用邻接表或者链式前向星这一类数据结构，来记录图的信息，可以做到只遍历与该顶点相连的顶点。
Read full article from 算法总结之拓扑排序 - Enumz - 博客园
No comments:
Post a Comment