Condition: undirected graph
An arbitrary point as the start, will all sides to the point at which a priority queue, said edge to be unlocked, pop up an edge from the queue (minimum) must be to see if the edge has tags, if without markup tags, said this side is needed, and then will be connected to the edge of another point connected to unlock all of the edge,, and so on
The diagram is represented and generated in: click on the open link
import java.util.Comparator; import java.util.HashSet; import java.util.PriorityQueue; import java.util.Set; public class primMST { public static class EdgeComparator implements Comparator<Edge> { @Override public int compare(Edge o1, Edge o2) { return o1.weight - o2.weight; } } public static Set<Edge> prime(Graph graph) { PriorityQueue<Edge> pQueue = new PriorityQueue<Edge>(new EdgeComparator()); HashSet<Edge> edges = new HashSet<Edge>(); HashSet<Node> nodes = new HashSet<Node>(); For (Node Node: graph.nodes.values()) {// set if (! Nodes.contains (node)) {// Add set nodes.add(node); For (Edge curEdge: node.edges) {pqueue.add (curEdge); } while (! Pqueue.isempty ()) {// Popup a minimum weight Edge (queue is not empty) Edge Edge = pqueue.poll (); Node toNode = edge.to; if (! nodes.contains(toNode)) { nodes.add(toNode); edges.add(edge); For (Edge nextEdge: tonode.edges){pqueue.add (nextEdge); } } } } } return edges; }}Copy the code