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

2019年8月1日 星期四

[ Minimum Spanning Tree, kruskal, prim ] 最小生成樹經典演算法

以前覺得這應該是很簡單的東西,但我發現網路上使用priority_queue的prim演算法相關程式碼我覺得寫不好,我就把我自己的放上來。這裡順便也放上kruskal的程式碼。

prim $\ord{\left(\abs{V}+\abs{E}\right)\log{\abs{V}}}$:
kruskal $\ord{\abs{V}+\abs{E}\log{\abs{E}}}$:

沒有留言:

張貼留言