[問題] 有關dict用法 (DFS找有向圖中的cycle)
我想要改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
→
11/11 07:34,
5年前
, 1F
11/11 07:34, 1F
→
11/11 07:36,
5年前
, 2F
11/11 07:36, 2F
→
11/11 12:39,
5年前
, 3F
11/11 12:39, 3F
→
11/11 12:39,
5年前
, 4F
11/11 12:39, 4F
※ 編輯: skyHuan (223.140.71.48), 11/11/2018 16:39:06
→
11/11 17:28,
5年前
, 5F
11/11 17:28, 5F
→
11/11 17:29,
5年前
, 6F
11/11 17:29, 6F
→
11/11 17:31,
5年前
, 7F
11/11 17:31, 7F
→
11/11 17:31,
5年前
, 8F
11/11 17:31, 8F
→
11/11 18:29,
5年前
, 9F
11/11 18:29, 9F
→
11/11 18:29,
5年前
, 10F
11/11 18:29, 10F