# 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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://garychang.gitbook.io/data-structure/4-graph/4.3-spanning-tree.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.