在圖論中,無向圖 G 的生成樹(英語:Spanning Tree)是具有 G 的全部頂點,但邊數最少的連通子圖。[1] 此條目需要補充更多來源。 (2020年3月8日) 格子圖(英語:grid graph)的生成樹(圖中的藍色粗線) 8x8網格圖上的三個例子 以 V {\displaystyle V} 表示頂點, E {\displaystyle E} 表示邊,若圖 G = ( V ( G ) , E ( G ) ) {\displaystyle G=(V(G),E(G))} 和樹 T = ( V ( T ) , E ( T ) ) {\displaystyle T=(V(T),E(T))} ,有 E ( T ) ⊂ E ( G ) {\displaystyle E(T)\subset E(G)} 和 V ( G ) = V ( T ) {\displaystyle V(G)=V(T)} ,那麼 T {\displaystyle T} 是 G {\displaystyle G} 的生成樹。 一個圖的生成樹可能有多個。 帶權圖的生成樹中,總權重最小的稱為最小生成樹。 求取最小生成樹的算法: 克魯斯克爾演算法 - 一種貪心算法,複雜度是 O ( E log E ) {\displaystyle O(E\log {E})} 。 普林姆算法 - 另一種貪心算法,用二叉堆優化時複雜度是 O ( E + V log V ) {\displaystyle O(E+V\log {V})} 。當邊數遠遠大於點數,可近似認為是 O ( E ) {\displaystyle O(E)} 。這是一篇電腦科學小作品。您可以透過編輯或修訂擴充其內容。閱論編 [1]第23章. 算法导论 第三版. : 362. ISBN 978-7-111-40701-0.