最小生成樹定義

最小生成樹（Minimum Spanning Tree, MST）是在給定的帶權有向圖或無向圖中，找出總權值最小的樹，這棵樹包含了圖的所有頂點。最小生成樹可以用來解決一些實際問題，例如在電網中找到成本最低的布線方案，或者在通信網絡中找到開銷最小的中樞節點連接方式。

最小生成樹有幾個特點：

1. 樹形結構：最小生成樹是一棵樹，它連接了圖的所有頂點，且沒有循環。
2. 包含所有頂點：最小生成樹包含了圖的所有頂點。
3. 總權值最小：最小生成樹的所有邊的權值之和最小。

最小生成樹的算法有多種，其中最著名的是普里姆（Prim）算法和克魯斯卡爾（Kruskal）算法。這些算法可以有效地在給定的圖中找到最小生成樹。