wuvin
Always take risks!
Toggle navigation
wuvin
主页
实验室的搬砖生活
机器学习
公开的学术内容
公开的其他内容
About Me
归档
标签
友情链接
ZYQN
ihopenot
enigma_aw
hzwer
杨宗翰
DFS版拓扑排序
? 知识点 ?
? 图论 ?
2017-03-19 19:01:06
1208
0
0
wuvin
? 知识点 ?
? 图论 ?
我不得不得不说这是一种神奇拓扑序生成方式。 我们沿着有向边反着走，假设我们搜索到了u，那么下一步会搜索所有指向u的点,因为只要这些点存在就还不能把u加入拓扑序中。 思路如下： ``` function DFS(int u){ for(所有通过有向边可以到达u的点v){ 如果v没有被删掉 DFS(v);//访问完后v会被删掉 } 把u加入拓扑序中 删掉当前点u（可以采用打标记的方式） } ``` 当然我们还可以开一下脑洞 **为什么不能就顺着来呢？然后把得到的拓扑序列反转呢！** 事实证明这是可以的。poj2367板题可以过。（有special judge） 那么我们还是来证明一下正确性吧： 对于原拓扑序列，该序列只有一个要求及：如果u是v的祖先（反着就是有一条从u到v的路径），那么在拓扑序中u必须比v先出现，而DFS就可以满足这个需求，在递归完成之前是绝不会被输出的，而该点的DFS可以访问到它所有的祖先。而现在我们把图正向序列反向也可以保证子孙先比祖先后出现。**现在正在访问的点永远会比它可以到达的点先输出。** 速度上这个办法的常数是明显大于常规拓扑排序的。 <font size=1>2016-02-05<font>
上一篇:
图的连通1(缩点)
下一篇:
对偶图
0
赞
1208 人读过
新浪微博
微信
腾讯微博
QQ空间
人人网
提交评论
立即登录
, 发表评论.
没有帐号?
立即注册
0
条评论
More...
文档导航
wuvin
没有帐号? 立即注册