最小生成樹kruskal

Kruskal算法是一種用於在加權無向圖中找出最小生成樹的算法。它的基本思想是從所有邊中選擇權值最小的邊，如果這條邊連線的兩個頂點已經在最小生成樹中通過其他邊連線，則捨棄這條邊。重複這個過程，直到找到一個包含所有頂點的最小生成樹為止。

以下是Kruskal算法的基本步驟：

1. 將所有邊按照權值從小到大排序。
2. 創建一個空的森林（即由不相交的樹組成的集合），並將所有頂點添加到森林中。
3. 遍歷排序後的邊，對於每條邊，如果它連線的兩個頂點在森林中分別屬於不同的樹，那麼就將這條邊加入到相應的樹中，並更新這棵樹的最小生成樹權值。
4. 重複步驟3直到森林中只剩下一個樹，這個樹就是最小生成樹。

Kruskal算法的時間複雜度為O(ElogE)，其中E是邊的數量。這是因為每次選擇一條邊時，需要遍歷所有的邊以確定它是否與已有的樹相連。空間複雜度也是O(E)，因為需要存儲所有的邊和樹的結構。

需要注意的是，Kruskal算法只適用於無向圖和權值非負的邊。如果圖中存在環或者邊的權值可以為負數，那麼需要使用其他算法來找出最小生成樹，如Prim算法。