在圖論中,無向圖 G 的生成樹(英語:Spanning Tree)是具有 G 的全部頂點,但邊數最少的連通子圖。[1]
以 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} 的生成樹。
一個圖的生成樹可能有多個。
帶權圖的生成樹中,總權重最小的稱為最小生成樹。
求取最小生成樹的算法: