Python 判断 有向图 是否有环

Question

如题所述

Answer 1

判断是否有环，思想方法是，从任一点开始遍历，譬如按右遍历进行，在每一个分叉点，都往右走，并记录走过的轨迹，这样走下去会出现两种情况，一种是走到头了，没遇上前面已经走过的点，这时撤回到离末端最近的一个分叉点并按右往左顺序的第2条路径继续遍历…………，如此不停的进行下去，直到全部走完，如果全部走完都没有碰到已经走过的点的话，说明没有环。否则就有环