Prim's Algorithm

Java code:

import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;

class Edge {
    int startVertex, endVertex, weight;
}

class PriQueueComparator implements Comparator<Edge> {

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

public class PrimAlgorithm {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int vertexNum;
        int nextVertex;
        Set<Integer> used = new HashSet<Integer>();
        Map<Integer, Map<Integer, Integer>> graph = new HashMap<Integer, Map<Integer, Integer>>();
        Map<Integer, Map<Integer, Integer>> minSpanTree = new HashMap<Integer, Map<Integer, Integer>>();
        Queue<Edge> priQueue;
        
        try {
            System.out.print("please input the number of total vertexes:");
            vertexNum = sc.nextInt();
            priQueue = new PriorityQueue<Edge>(vertexNum - 1, new PriQueueComparator());
            System.out.println("please input the graph:");
            for (int i=1; i<=vertexNum; i++)
                graph.put(i, new HashMap<Integer, Integer>());
            for (int i=1; i<=vertexNum; i++) {
                for (int j=1; j<=vertexNum; j++) {
                    String input = sc.next();
                    
                    if (input.equals("i"))
                        graph.get(i).put(j, Integer.MAX_VALUE);
                    else
                        graph.get(i).put(j, Integer.parseInt(input));
                }
            }
        } 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);
        }
        nextVertex = 1;
        while (true) {
            Edge smallestEdge;
            
            used.add(nextVertex);
            if (used.size() == vertexNum)
                break;
            for (int i=1; i<=vertexNum; i++) {
                Edge theEdge = new Edge();
                
                if (graph.get(nextVertex).get(i) != Integer.MAX_VALUE) {
                    theEdge.startVertex = nextVertex;
                    theEdge.endVertex = i;
                    theEdge.weight = graph.get(nextVertex).get(i);
                    priQueue.add(theEdge);
                }
            }
            while (true) {
                smallestEdge = priQueue.poll();
                if (!used.contains(smallestEdge.endVertex))
                    break;
            }
            minSpanTree.get(smallestEdge.startVertex).put(smallestEdge.endVertex, smallestEdge.weight);
            minSpanTree.get(smallestEdge.endVertex).put(smallestEdge.startVertex, smallestEdge.weight);
            nextVertex = smallestEdge.endVertex;
        }
        System.out.println("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();
        }
    }
}

範例輸入輸出:

---

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