【圖論筆記】克魯斯卡爾算法（Kruskal）求最小生成樹

適用于

克魯斯卡爾適合用來求邊比較稀疏的圖的最小生成樹

簡記：

將邊按照升序排序，選取n-1條邊，連通n個頂點。
添加一條邊的時候，如何判斷能不能添加這條邊？（添加進來之后，會不會構成回路）
看標記，
和原來的標記不一樣，就可以加入，
加入之后將他們的標記修改為一樣的。

圖解

第一步:創建一個連通圖，并且給每個頂點都標記上不同的顏色

第二步：選取邊<A,C>,選完之后C的顏色要和A相同

第三步：加入邊<D,F>,將F的顏色改為D的藍色

第四步：加入邊<B,E>，將E改為紫色

第五步：添加邊<C,F>，將F相連的節點改為綠色（包括它自己）

第六步：<A,D>不能加入，因為A和D的顏色一樣。加入邊<B,C>，將原來和B相連的節點的顏色都改為綠色。完

代碼正在研究