[問題] 有關dict用法 (DFS找有向圖中的cycle)

[skyHuan (Huan)]

我想要改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://www.ptt.cc/bbs/Python/M.1541865645.A.A9F.html
→ bowin: 建議你可以直接研究Introduction to Algorithms,檢查DAG就n
→ bowin: 是把notices依postvisite id從大到小排序的結果
→ skyHuan: 我是想找已經有cycle的圖然後把他列出來
→ skyHuan: DAG原本就是無cycle的不知道能不能用><
※ 編輯: skyHuan (223.140.71.48), 11/11/2018 16:39:06
→ bowin: 不好意思我想成topological sort了
→ bowin: Check DAG應該是每次遇到neighbor vertice就檢查previsitId
→ bowin: 若neighbor的previsit id < current的previst id
→ bowin: 表示之前visit過，則非DAG
→ skyHuan: 我的那段code有用到類似的概念，我就是靠previsit去找cyc
→ skyHuan: le的，但結果還是有點錯><