我想要改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
是我想到的方法还有什么有问题的地方吗><
小的初学菜逼八不懂比较多
麻烦各位前辈指教
感谢万分

建议你可以直接研究Introduction to Algorithms,检查DAG就n是把notices依postvisite id从大到小排序的结果

我是想找已经有cycle的图然后把他列出来DAG原本就是无cycle的不知道能不能用><

不好意思我想成topological sort了Check DAG应该是每次遇到neighbor vertice就检查previsitId若neighbor的previsit id < current的previst id表示之前visit过，则非DAG

我的那段code有用到类似的概念，我就是靠previsit去找cycle的，但结果还是有点错><