[理工] 108 交大資演 題組 12

作者: kyh436 (你快看)   2023-01-07 18:00:59

想請問第25題的部分,為什麼第二個 while 每次都要執行 O(|E|) 次的 BFS?
是因為 augmenting path 最多就是點的排序,所以有O(|V|^2 ) = O(|E|)嗎?
謝謝大家~
作者: mathtsai (mathtsai)   2023-01-07 19:57:00
知道BFS複雜度就知道啦
作者: codepo (codenfu)   2023-01-31 00:18:00
令e=(vi , vj), I ≠ j, 每一個點與其他點相連的邊用 adjacent list 表示,則每次在找邊時可能花 O(E) 時間

Links booklink

Contact Us: admin [ a t ] ucptt.com