\( \newcommand{\ord}[1]{\mathcal{O}\left(#1\right)} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\ceil}[1]{\lceil #1 \rceil} \newcommand{\opord}{\operatorname{\mathcal{O}}} \newcommand{\argmax}{\operatorname{arg\,max}} \newcommand{\str}[1]{\texttt{"#1"}} \)

2015年10月14日 星期三

[ Edmonds–Karp algorithm ,Flow] 網路流Edmonds–Karp算法

這是最基本的多項式時間網路流演算法,因此在這裡我多了一些變化,首先是一般用鄰接矩陣,複雜度$\ord{\abs{V}^5}$的做法:
接著是使用鄰接串列,複雜度是$\ord{\abs{E}^2\abs{V}}$的作法:
最近幫學長寫作業的時候,又發現了一個不需要多紀錄反邊的做法,但是每個點要同時記錄入邊和出邊,這樣可以用較少的記憶體完成演算法:

沒有留言:

張貼留言