生成樹 — Spanning Tree
如果是第一次接觸的話，應該會對Spanning Tree這詞，感到很陌生。所以這次要帶各位來了解什麼叫做生成樹。
在看這篇之前，建議請先了解一下圖的結構是什麼，再來看會沒那麼複雜，因為會用到一些專有名詞。
什麼是生成樹？
先用例子來解釋，現在我們有一個圖(Graph)稱為G，如下圖：
而生成樹就是
1. 新建一個圖，包含圖 G的所有「點(Vertex)」（這邊就是A, B, C, D）
2. 將所有「點」連接再一起，即為生成樹。（要特別注意，要用最少的邊(Edge)連接再一起才會是生成樹）
另一種想法是，可以連接每一個點而且用的是最少的邊。（這個概念可以想成郵差送信，每一戶(Vertex)都要去，但又想要花最少的時間(edges)）
如果看不懂沒關係，看下面的圖就能理解是什麼意思。
上面的四個圖，皆為圖G的生成樹。
生成樹的性質
從上面的圖來看，我們知道一個圖的生成樹不一定只有一個，有可能會有很多個生成樹。
得到一些性質：
1. 一個圖(Graph)不只會有一個生成樹(Spanning Tree)
2. 同一個圖的生成樹，會有相同的點 (Vertex), 邊(Edge)的個數。
3. 所有的生成數，不會出現 Cycle, loop的結構。
4. 如果把其中一個「邊(Edge)」拿掉就會成為無連通圖(Disconnected Graph)我們可以說生成樹是最小的連接(minimally connected)
5. 只要多加一個邊，就會形成cycle, Loop，所以也可以成生成樹是maximally acyclic(最大無環)
生成樹通常會應用在哪裡？
通常是網路方面的應用，我們可以將每一台電腦看作是一個「點(Vertex)」如果要將很多電腦連接再一起的時候，這時候就可以形成像圖一樣的結構。
＊Civil Network Planning
＊Computer Network Routing Protocol
通常介紹完生成樹後，會提到最小生成樹(Minimum Spanning Tree)
最小生成樹(Minimum Spanning Tree, MST)
概念也是從一個圖Ｇ中，找到另一個圖，而這個圖稱為最小生成樹。
那要怎麼找最小生成樹？
在權重圖中，最小生成樹：
- 將全部「點(Vertex)」相連。
- 相連的「邊(Edge)」其權重(Weigh)要最小，即為最小生成樹。
（＊權重的概念是距離的遠近、中間的成本等等。）
上面舉的是很簡單的例子，但我們知道現實生活是不會這麼單純的，所以我們就會有演算法去找最小成樹。
之後就會來介紹兩種普遍尋找最小生成樹的演算法：
- Kruskal’s Algorithm
- Prim’s Algorithm
希望這篇文章可以幫助到正在學習的夥伴，筆者我一開始學的時候，對這個名詞超級陌生，上網找了很久也不知道在幹嘛，果然還是需要時間的積累，才可以了解其中的意義。如果現在還不懂的話，也不用灰心，多多接觸就可以的！
