现在的位置: 首页 > 综合 > 正文

判断有向图是否包含环路

2014年10月03日 ⁄ 综合 ⁄ 共 251字 ⁄ 字号 评论关闭
问题:
RT,这个问题是我在思考算导上某练习题后联想到的。(可参考前一篇文章)
做法:
显而易见,我们可以对这个有向图进行拓扑排序,如果拓扑排序不能完成对顶点的排序(出现了后向边),说明该图存在环。
当然为了锻炼思维能力(明明是吃饱了撑的),我进行了另外的思考。
比如强连通分量,我们可以求出这个有向图的强连通分量,如果它的强连通分量数量小于|V|,说明有两个以上的点被并到同一个强连通分量中,而同一个强连通分量中的任意两点可以互相到达,说明该图肯定存在环路。
貌似直接DFS是不行的,如果要用DFS肯定要改一下。

【上篇】
【下篇】

抱歉!评论已关闭.