Python 判断 有向图 是否有环

Python017

Python 判断 有向图 是否有环,第1张

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

现在有13个人围成一个环,从1开始报数,数到3的人离开,写出程序计算最后剩下的是谁。

使用while循环

使用for循环

使用递归

摒弃递归,每次步长不为k时候都把当前元素弹出并放到队列尾部,从而模拟循环链表结构。进一步优化,由于列表弹出第一个元素的复杂度较高,可以使用双端队列来进行优化: