> 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.

![](https://2769815795-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGckN3OAfinKuVIrkMj%2F-LIiwEMEnifCCaWGWASf%2F-LIiwHrEPtKusjIsvH-T%2F%E8%9E%A2%E5%B9%95%E5%BF%AB%E7%85%A7%202018-07-31%2014.04.43.jpg?alt=media\&token=5f365f91-390e-40c9-98e5-512f261aa977)

<img src="https://2769815795-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGckN3OAfinKuVIrkMj%2F-LIjozg53VxvyHDTFlI7%2F-LIjpKsMuH8Y8QWQo_wf%2F%E8%9E%A2%E5%B9%95%E5%BF%AB%E7%85%A7%202018-07-31%2018.14.14.jpg?alt=media&amp;token=4278929c-4296-4d1c-a4f8-e47889325660" alt="" data-size="original"> DFS Spanning Tree<img src="https://2769815795-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGckN3OAfinKuVIrkMj%2F-LIjozg53VxvyHDTFlI7%2F-LIjpN1DGyEyFc7EA9T5%2F%E8%9E%A2%E5%B9%95%E5%BF%AB%E7%85%A7%202018-07-31%2018.14.39.jpg?alt=media&amp;token=48777089-7ad2-4b88-a883-37c73ee9979e" 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