跳至內容

生成樹

維基百科,自由的百科全書
格子圖英語grid graph的生成樹(圖中的藍色粗線)
8x8網格圖上的三個例子

圖論中,無向圖 G生成樹(英語:Spanning Tree)是具有 G 的全部頂點,但邊數最少的連通子圖。[1]

表示頂點表示,若圖 ,有,那麼的生成樹。

一個圖的生成樹可能有多個。

最小生成樹

帶權圖的生成樹中,總權重最小的稱為最小生成樹

求取最小生成樹的算法:

  • 克魯斯克爾演算法 - 一種貪心算法,複雜度是
  • 普林姆算法 - 另一種貪心算法,用二叉堆優化時複雜度是 。當邊數遠遠大於點數,可近似認為是
  1. ^ 第23章. 算法导论 第三版. : 362. ISBN 978-7-111-40701-0.