我想要改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的，但結果還是有點錯><