作者kyh436 (你快看)
看板Grad-ProbAsk
標題[理工] 108 交大資演 題組 12
時間Sat Jan 7 18:00:59 2023
https://imgur.com/l6GOxNP
想請問第25題的部分，為什麼第二個 while 每次都要執行 O(|E|) 次的 BFS?
是因為 augmenting path 最多就是點的排序，所以有O(|V|^2 ) = O(|E|)嗎?
謝謝大家~
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.113.123.81 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1673085661.A.CE1.html
1F：→ mathtsai: 知道BFS複雜度就知道啦 01/07 19:57
2F：推 codepo: 令e=(vi , vj), I ≠ j, 每一個點與其他點相連的邊用 adj 01/31 00:18
3F：→ codepo: acent list 表示，則每次在找邊時可能花 O(E) 時間 01/31 00:18