ds圖—最小生成樹_Java: Kruskal算法生成最小生成樹(鄰接矩陣)

Java: Kruskal算法生成最小生成樹(鄰接矩陣):

package 
           

輸出： Kruskal=36: (E,F) (C,D) (D,E) (B,F) (E,G) (A,B) 分析：

Java: Kruskal算法生成最小生成樹(鄰接矩陣)
克魯斯卡爾(Kruskal)算法
Kruskal算法和Prim算法相比，就是Kruskal算法從邊出發，不斷尋找目前未添加進Et的、且權值最小的邊，若添加後不形成環，則添加成功；
因為形成環，說明已經是連同了，這條邊是不需要的。否則跳過，
繼續嘗試添加下一條邊。最後，判斷邊的數量arcnum是否是點的數量vexnum-1，若是則最小生成樹構造成功，否則失敗。
Prim算法與頂點相關時間複雜度O（|V|2），是以适合頂點少邊多的圖；
Kruskal反之，算法與邊相關，時間複雜度為O（|E|log|E|），是以适合邊少頂點多的圖；
           

圖解：