\( \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"}} \)

2016年7月15日 星期五

[ Edmonds's general graph matching algorithm ] 一般圖最大匹配

關於匹配的教學我全部寫在這份投影片裡了:https://jacky860226.github.io/general-graph-weighted-match-slides/#/
所以這裡直接提供模板:
注意這裡必須要是無向圖
張貼者： 於
標籤： ,

1 則留言:

  1. FHVirus2024年3月4日 清晨6:32

    日月卦長您好，我想請問為什麼這份程式碼的複雜度是 O(V(E + V)) 的？第 18 行的 u = pa[v]; 看起來會爬過半個 blossom，在層層堆疊的 blossom 中可能會有邊被爬過 O(V) 次，這樣有可能會退化至 O(V^2(E + V))，但我構造不出反例 ><

    回覆刪除

訂閱： 張貼留言 (Atom)