Kruskal's Algorithm

Java code:

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

class Edge implements Comparable<Edge> {
    int startVertex, endVertex, weight;

    @Override
    public int compareTo(Edge otherEdge) {
        if (weight < otherEdge.weight)
            return -1;
        else if (weight == otherEdge.weight)
            return 0;
        else
            return 1;
    }
}

public class KruskalAlgorithm {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int vertexNum;
        int countEdge;
        int totalEdge;
        List<Edge> allEdgeList = new ArrayList<Edge>();
        Map<Integer, Map<Integer, Integer>> minSpanTree = new HashMap<Integer, Map<Integer, Integer>>();
        
        try {
            System.out.print("please input the number of total vertexes:");
            vertexNum = sc.nextInt();
            System.out.println("please input the graph:");
            for (int i=1; i<=vertexNum; i++) {
                for (int j=1; j<=vertexNum; j++) {
                    String theWeight = sc.next();
                    
                    if (!theWeight.equals("i") && i < j) {
                        Edge theEdge = new Edge();
                        
                        theEdge.startVertex = i;
                        theEdge.endVertex = j;
                        theEdge.weight = Integer.parseInt(theWeight);
                        allEdgeList.add(theEdge);
                    }
                }    
            }
        } finally {
            sc.close();
        }
        for (int i=1; i<=vertexNum; i++) {
            minSpanTree.put(i, new HashMap<Integer, Integer>());
            for (int j=1; j<=vertexNum; j++)
                minSpanTree.get(i).put(j, Integer.MAX_VALUE);
        }
        Collections.sort(allEdgeList);
        countEdge = 0;
        totalEdge = vertexNum - 1;
        while (countEdge != totalEdge) {
            Edge smallestEdge = allEdgeList.remove(0);
            
            if (!checkCycle(minSpanTree, vertexNum, smallestEdge.startVertex, smallestEdge.startVertex, smallestEdge.endVertex)) {
                minSpanTree.get(smallestEdge.startVertex).put(smallestEdge.endVertex, smallestEdge.weight);
                minSpanTree.get(smallestEdge.endVertex).put(smallestEdge.startVertex, smallestEdge.weight);
                countEdge++;
            }
        }
        System.out.println("the minimal spanning tree:");
        for (int i=1; i<=vertexNum; i++) {
            for (int j=1; j<=vertexNum; j++) {
                if (minSpanTree.get(i).get(j) == Integer.MAX_VALUE)
                    System.out.printf("%3s", "i");
                else
                    System.out.printf("%3d", minSpanTree.get(i).get(j));
            }
            System.out.println();
        }
    }
    
    private static boolean checkCycle(Map<Integer, Map<Integer, Integer>> minSpanTree, int vertexNum, int originalVertex, int preVertex, int nowVertex) {
        if (originalVertex == nowVertex)
            return true;
        else {
            for (int i=1; i<=vertexNum; i++) {
                if (minSpanTree.get(nowVertex).get(i) != Integer.MAX_VALUE && i != preVertex && checkCycle(minSpanTree, vertexNum, originalVertex, nowVertex, i))
                    return true;
            }
            return false;
        }
    }
}

範例輸入輸出:

---

抱歉沒空說明程式碼，只能說明一下輸入輸出的部份。首先輸入圖形上總共點的數量，再輸入相鄰矩陣，橫軸表示點1~點10，縱軸也是表示點1~點10，輸入的是點到點之間的權重，若輸入i表示這兩點不相連，也就是權重無限大。輸出結果也是相鄰矩陣，表示找到的最小成本擴展樹。本範例輸入是採用課本習題2的圖，所以可以參照課本的圖方便了解。