> For the complete documentation index, see [llms.txt](https://garychang.gitbook.io/data-structure/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://garychang.gitbook.io/data-structure/4-graph/4.3-spanning-tree.md).

# 4.3 - Spanning Tree

### 1. Spanning Tree

$$G=(V, E)$$ 是一個**Connected**的Undirected Graph，令 $$S=(V, T)$$是G的一個Spanning Tree:

1. $$E=T+B \Rightarrow T=E-B$$ 

   T: Tree edge；B: Back edge
2. 自B中挑選一個邊加入S中，必在S中形成一個cycle。
3. 在S中的任何頂點對之間，存在一條唯一的Simple Path。

e.g.

![](/files/-LIiwHrEPtKusjIsvH-T)

<img src="/files/-LIjpKsMuH8Y8QWQo_wf" alt="" data-size="original"> DFS Spanning Tree<img src="/files/-LIjpN1DGyEyFc7EA9T5" alt="" data-size="original"> BFS Spanning Tree

1. 任何Connected Undirected Graph至少有一棵Spanning Tree
2. 若Connected Undirected Graph有v個頂點，則Spanning Tree的邊數必為v-1條邊
3. 若將Binary Tree視為無向圖，則它的Spanning Tree只有一棵
4. 若為unconnected graph，則必無Spanning Tree

### 2. Min Spanning Tree(最小成本展開樹)

Connected Undirected Graph $$G=(V, E)$$ 的每個邊上cost值，則在Ｇ的所有spanning trees中具有邊成本總和最小者。

1. min spanning tree ≥ 1
2. 若G中每個邊的成本皆不同，則最小成本展開數樹只有一棵

求法:&#x20;

1. Kruskal's algorithm
2. Prim's algorithm
3. Sollin's algorithm