Minimum Spanning Tree

Definition

A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is as small as possible.

Demo code: Kruskal Algorithm

import java.util.*;
import java.lang.*;

class Edge{
        String node1;
        String node2;
        int cost;
        public Edge(String a, String b, int c){
            node1 = a;
            node2 = b;
            cost = c;
        }
    }
/*
 * Implement Kruskal MST Algorithm in Java:
 *         1. sort edges in ascending order. 
 *        2. Initialize Set U={} to store the result edges
 *         3. pick up one edge every time, if the two vertices doesn't form a cycle upon U, add the edge to U;
 *        4. If U size reaches N-1 (N is the number of vertex), End;
 */

public class mst{
    public static ArrayList<Edge> getmst(ArrayList<Edge> graph){
        ArrayList<Edge> res=new ArrayList<Edge>();
        if(graph==null || graph.size()==0) return res;

        /* 
         * Help structure used for checking whether two vertices is in the same subset
         */
        Map<String,String> father=new HashMap<String,String>();
        for(Edge a : graph) {
            father.put(a.node1, a.node1);
            father.put(a.node2, a.node2);
        }
        Collections.sort(graph, new Comparator<Edge>(){
            @Override
            public int compare(Edge a, Edge b){
                if(a.cost==b.cost){
                    if(a.node1.equals(b.node1)) return a.node2.compareTo(b.node2);
                    else return a.node1.compareTo(b.node1);
                }else return a.cost-b.cost;
            }
        });
        for(Edge tmp : graph){
            String root1=Findroot(father, tmp.node1);
            String root2=Findroot(father, tmp.node2);
            if(!root1.equals(root2)){
                father.put(root2,root1);
                res.add(tmp);
            }
        }
        /* Check if this graph is connected Graph by check if all the nodes are in the same set */
        String root=null;
        for(String node: father.keySet()){
            String tmp=Findroot(father, node);
            if(root==null) root=tmp;
            else{
                if(!root.equals(tmp)) return new ArrayList<Edge>(); // Graph is not connected
            }
        }
        return res;
    }

    public static String Findroot(Map<String,String> father, String node){
        String ptr=node;
        while(!father.get(ptr).equals(ptr)){
            father.put(ptr, father.get(father.get(ptr)));// path compression
            ptr=father.get(ptr);
        }
        return ptr;
    }
    /* 
     * Test out structure
     */
    public static void main(String[] args) {
        ArrayList<Edge> edges = new ArrayList<>();
        edges.add(new Edge("A","B",6));
        edges.add(new Edge("B","C",4));
        edges.add(new Edge("C","D",5));
        edges.add(new Edge("D","E",8));
        edges.add(new Edge("E","F",2));
        edges.add(new Edge("B","F",10));
        edges.add(new Edge("E","C",9));
        edges.add(new Edge("F","C",7));
        edges.add(new Edge("B","E",3));
        edges.add(new Edge("A","F",16));
        edges.add(new Edge("H","A",2));
        ArrayList<Edge> res = new mst().getmst(edges);
        for (Edge c : res){
            System.out.println(c.node1 + " -> " + c.node2 + " " + c.cost);
        }
    }
}