作者skyHuan (Huan)
看板Python
标题[问题] 有关dict用法 (DFS找有向图中的cycle)
时间Sun Nov 11 00:00:41 2018
我想要改DFS演算法来找有向图有没有cycle
这是我的code：
https://pastebin.com/6G5FL7DQ
我的判断法是有back edge就表示有cycle
就从这个edge开始回推找DFS的父点
直到找到起点为止，如code 49~58行
我表示图的方法是用dict表示相邻串列
https://imgur.com/YrOsr66.jpg
G = { 'P1': ['P2'], 'P2': ['P4', 'P5', 'P3'], 'P3': ['P4'], 'P4': ['P1'],
'P5': [] }
如上面图的例子就用dict表示对应到的边
然後为了DFS方便建立一个表示graph的class
程式可以执行，在第63~65行有印出结果
但return回findCycle()之後东西就不见了
而且return後也不是空list而是None
另外在63~65行测试印的结果
有些cycle是正确找到的但有些会有点怪
像我有其中一个测资找到的cycle list里面竟然有None
https://imgur.com/uTjVFfC.jpg
是我想到的方法还有什麽有问题的地方吗><
小的初学菜逼八不懂比较多
麻烦各位前辈指教
感谢万分
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 223.136.91.122
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Python/M.1541865645.A.A9F.html
1F：→ bowin: 建议你可以直接研究Introduction to Algorithms,检查DAG就n11/11 07:34
2F：→ bowin: 是把notices依postvisite id从大到小排序的结果11/11 07:36
3F：→ skyHuan: 我是想找已经有cycle的图然後把他列出来11/11 12:39
4F：→ skyHuan: DAG原本就是无cycle的不知道能不能用><11/11 12:39
※ 编辑: skyHuan (223.140.71.48), 11/11/2018 16:39:06
5F：→ bowin: 不好意思我想成topological sort了 11/11 17:28
6F：→ bowin: Check DAG应该是每次遇到neighbor vertice就检查previsitId 11/11 17:29
7F：→ bowin: 若neighbor的previsit id < current的previst id 11/11 17:31
8F：→ bowin: 表示之前visit过，则非DAG 11/11 17:31
9F：→ skyHuan: 我的那段code有用到类似的概念，我就是靠previsit去找cyc 11/11 18:29
10F：→ skyHuan: le的，但结果还是有点错>< 11/11 18:29