C最小生成樹

在圖論中，最小生成樹（Minimum Spanning Tree, MST）是一個連通圖的子圖，它包含所有頂點，且邊的權值總和最小。最小生成樹問題的目標是在給定的加權圖中找到這樣的一個樹。

最小生成樹有許多應用，例如在電力網路的設計中，可以找到成本最低的布線方案；在通信網絡中，可以找到開銷最小的中樞節點連接方案。

最小生成樹的一種常用算法是普里姆（Prim）算法，它從圖中的一個任意頂點開始，逐次添加邊，每次添加邊時都選擇權值最小的邊，直到構成一個包含所有頂點的連通子圖。

另一種常用的算法是克魯斯卡爾（Kruskal）算法，它按照邊的權值從小到大排序，然後逐個添加邊，只要邊的添加不會形成環路。

這些算法都可以保證找到加權圖的最小生成樹，並且在邊的權值是非負數的前提下，最小生成樹是唯一的。如果邊的權值中有負數，則最小生成樹可能不是唯一的，也可能不存在。