作者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://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1549802441.A.72A.html
1F:推 alen0303: path和寻访顺序是两回事 你寻访过程一定都会记录父点 02/10 20:47
原来~ 那所以说一次BFS只能记录一次父点 要跑多次才能有多条的意思吗 这样相同长
度也没有固定顺序?
※ 编辑: hanhancute (1.163.44.86), 02/10/2019 20:59:39
2F:→ jasonx12x: 跑一次BFS就可以了吧 02/10 21:06
3F:→ jasonx12x: 我的想法是用find往上找父点 02/10 21:06
L大谢谢! 很清楚~ 也谢谢其他大大
※ 编辑: hanhancute (1.163.44.86), 02/10/2019 23:22:25