作者hanhancute (Hanhan)
看板Grad-ProbAsk
標題[理工] BFS問題
時間Sun Feb 10 20:40:38 2019
各位大大晚安
我對max flow 的 EdmanKarp有小小的疑惑
https://imgur.com/TyS9gRG
用這題來說我的疑問
很值觀的
如果考試我會直接取 0 1 3 5 ， 0 2 4 5...
可是如果我用 BFS 去思考
(Queue的方式:取出ouptut後 放入取出點的連接點)
-- --- --- ---- ---
0 1 2 2 3 3 4 4 5
-- --- --- ---- ---
output:0 1 2 3 4 5
有點難理解他BFS怎麼取的? 可以取到 0 1 3 5
( 好像有點難表達我的疑惑QQ
謝謝~~
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.163.44.86
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1549802441.A.72A.html
推 alen0303: path和尋訪順序是兩回事 你尋訪過程一定都會記錄父點 02/10 20:47
原來~ 那所以說一次BFS只能記錄一次父點 要跑多次才能有多條的意思嗎 這樣相同長
度也沒有固定順序?
※ 編輯: hanhancute (1.163.44.86), 02/10/2019 20:59:39
→ jasonx12x: 跑一次BFS就可以了吧 02/10 21:06
→ jasonx12x: 我的想法是用find往上找父點 02/10 21:06
L大謝謝! 很清楚~ 也謝謝其他大大
※ 編輯: hanhancute (1.163.44.86), 02/10/2019 23:22:25