Java Implementation of Kruskal's algorithm for calculating the Minimum Spanning Tree (MST).

Hi Friends,

Lets see the Java Implementation of Kruskal's algorithm for calculating the Minimum Spanning Tree (MST).

I have used the concept of disjoint sets and path compression for the implementation.  The solution is based upon the discussion on geeksforgeeks :
http://www.geeksforgeeks.org/greedy-algorithms-set-2-kruskals-minimum-spanning-tree-mst/






 For the above graph we have MST as below :






Below is the Code for the implementation of the  algorithm.

public class KrushkalAlgorithm {
    
    public static void main(String[] args) {
        /* Let us create following weighted graph
        10
   1--------2
   |  \     |
  6|   5\   |15
   |      \ |
   3--------4
       4       */
        
        Graph graph = new Graph(4);
        graph.addVertex(1);
        graph.addVertex(2);
        graph.addVertex(3);
        graph.addVertex(4);
        graph.addEdge(1, 2, 10);
        graph.addEdge(1, 3, 6);
        graph.addEdge(1, 4, 5);
        graph.addEdge(3, 4, 4);
        graph.addEdge(2, 4, 15);
        graph.applyKrushkalAlgo();
    }
    public static class Graph {
        Vertex[] vertices;
        Edge edgeList;
        int maxSize;
        int size;
        int edgeNum;

        public Graph(int maxSize) {
            this.maxSize = maxSize;
            vertices = new Vertex[maxSize];
        }

        public class Vertex {
            int rank;
            Vertex representative;
            int name;
            Neighbour adj;

            Vertex(int name) {
                this.name = name;
                representative = this; // makeset
            }
        }

        public class Neighbour {
            int index;
            Neighbour next;
            int weight;

            Neighbour(int index, int weight, Neighbour next) {
                this.index = index;
                this.weight = weight;
                this.next = next;
            }
        }

        public class Edge {
            Vertex src;
            Vertex desti;
            Edge next;
            int weight;

            Edge(Vertex src, Vertex desti, int weight, Edge next) {
                this.src = src;
                this.desti = desti;
                this.weight = weight;
                this.next = next;
            }
        }

        public void addVertex(int name) {
            vertices[size++] = new Vertex(name);
        }

        public void addEdge(int src, int dest, int weight) {
            vertices[src - 1].adj = new Neighbour(dest - 1, weight, vertices[src - 1].adj);
            edgeList = new Edge(vertices[src - 1], vertices[dest - 1], weight, edgeList);
            edgeNum++;
        }

        public void applyKrushkalAlgo() {
            Edge[] edges = new Edge[edgeNum];
            int i = 0;
            while (edgeList != null) {
                edges[i] = edgeList;
                i++;
                edgeList = edgeList.next;
            }
            quicksort(edges, 0, edgeNum - 1);
            for (i = 0; i < edgeNum; i++) {
                Vertex u = findSet(edges[i].src);
                Vertex v = findSet(edges[i].desti);
                if (u != v) {
                    System.out.println(edges[i].src.name + " - " + edges[i].desti.name+" weight "+edges[i].weight);
                    union(u, v);
                }
            }
        }

        public Vertex findSet(Vertex u) {
            if (u.representative != u) {
                u.representative = findSet(u.representative); // path compression
            }
            return u.representative;
        }

        public void union(Vertex u, Vertex v) {
            if(u.rank == v.rank){
                v.representative = u;
                u.rank++;
            }else if(u.rank < v.rank){
                v.representative = u;
            }else{
                u.representative = v;
            }
        }

        public void quicksort(Edge[] edges, int start, int end) {
            if (start < end) {
                swap(edges, end, start + (end - start) / 2);
                int pIndex = pivot(edges, start, end);
                quicksort(edges, start, pIndex - 1);
                quicksort(edges, pIndex + 1, end);
            }
        }

        public int pivot(Edge[] edges, int start, int end) {
            int pIndex = start;
            Edge pivot = edges[end];
            for (int i = start; i < end; i++) {
                if (edges[i].weight < pivot.weight) {
                    swap(edges, i, pIndex);
                    pIndex++;
                }
            }
            swap(edges, end, pIndex);
            return pIndex;
        }

        public void swap(Edge[] edges, int index1, int index2) {
            Edge temp = edges[index1];
            edges[index1] = edges[index2];
            edges[index2] = temp;
        }
    }
}

Output :
3 - 4 weight 4
1 - 4 weight 5
1 - 2 weight 10

Hello friends,

Today I am here to here with implementation of Prim's Algorithm.

I have used MinHeap for the implementation and used bubble-up approach for accommodating the  changes done to any vertex which is already in the heap so as it bubbles up to its correct position in case its 'cost' has changed.

public class MSTRevisited {

    public static void main(String[] args) {
        Graph graph = new Graph(6);
        /*
         * graph.addNode('a'); graph.addNode('b'); graph.addNode('c');
         * graph.addNode('d'); graph.addNode('e'); graph.addNode('f');
         * graph.addEdege('a', 'b', 4); graph.addEdege('a', 'f', 2);
         * graph.addEdege('b', 'f', 3); graph.addEdege('b', 'c', 6);
         * graph.addEdege('c', 'f', 1); graph.addEdege('c', 'd', 3);
         * graph.addEdege('d', 'e', 2); graph.addEdege('f', 'e', 4);
         */
        graph.addNode('a');
        graph.addNode('b');
        graph.addNode('c');
        graph.addNode('d');
        graph.addEdege('a', 'b', 4);
        graph.addEdege('a', 'c', 2);
        graph.addEdege('b', 'c', 1);
        graph.addEdege('b', 'd', 2);
        graph.addEdege('c', 'd', 3);
        graph.applyPrimAlgo();
    }

    public static class Graph {
        private Vertex verticies[];
        private int maxSize;
        private int size;
        private HashMap map;
        private MinHeap Q;

        public Graph(int maxSize) {
            this.maxSize = maxSize;
            verticies = new Vertex[maxSize];
            map = new HashMap(maxSize);
            Q = new MinHeap(maxSize);
        }

        public void addNode(char data) {
            verticies[size] = new Vertex(data, size);
            map.put(data, size);
            size++;
        }

        public void addEdege(char sourceData, char destinationData, int weight) {
            int sourceIndex = map.get(sourceData);
            int destinationIndex = map.get(destinationData);
            verticies[sourceIndex].adj = new Neighbour(destinationIndex,
                    weight, verticies[sourceIndex].adj);
            verticies[destinationIndex].adj = new Neighbour(sourceIndex,
                    weight, verticies[destinationIndex].adj);
        }

        public void applyPrimAlgo() {
            // add all the keys to the Q

            PrimEdege pe = null;
            Vertex vertex = verticies[0];
            vertex.cost = 0;
            vertex.state = Vertex.IN_Q;
            Q.add(vertex);
            while (!Q.isEmpty()) {
                Vertex poppedVertex = Q.remove();
                poppedVertex.state = Vertex.VISITED;
                Neighbour temp = poppedVertex.adj;
                if (poppedVertex.parentIndex != -1) {
                    char source = verticies[poppedVertex.index].data;
                    char destination = verticies[poppedVertex.parentIndex].data;
                    pe = new PrimEdege(source, destination, pe);
                }
                while (temp != null) {
                    Vertex adjVertex = verticies[temp.index];
                    if (adjVertex.state != Vertex.VISITED) {
                        if (adjVertex.cost > temp.weight) {
                            adjVertex.cost = temp.weight;
                            adjVertex.parentIndex = poppedVertex.index;
                        }
                        if (adjVertex.state != Vertex.IN_Q) {
                            Q.add(adjVertex);
                            adjVertex.state = Vertex.IN_Q;
                        } else {
                            // bubble up this Node in the heap
                            Q.bubbleUp(adjVertex);
                        }
                    }
                    temp = temp.next;
                }
            }

            PrimEdege temp = pe;
            while (temp != null) {
                System.out.print("(" + temp.source + "," + temp.destination
                        + ") ");
                temp = temp.next;
            }
            System.out.println();
        }

        private static class PrimEdege {
            public char source;
            public char destination;
            private PrimEdege next;

            public PrimEdege(char source, char destination, PrimEdege next) {
                this.source = source;
                this.destination = destination;
                this.next = next;
            }
        }

        public static class MinHeap {
            private Vertex[] items;
            private int maxSize;
            private int size;

            public MinHeap(int maxSize) {
                this.maxSize = maxSize;
                items = new Vertex[maxSize];
            }

            public void bubbleUp(Vertex vertex) {
                // @TODO
                int i = 0;
                for (; i < size; i++) {
                    if (items[i] == vertex) {
                        break;
                    }
                }
                if (i < size) {
                    int currentIndex = i;
                    Vertex currentItem = items[currentIndex];
                    int parentIndex = (currentIndex-1) / 2;
                    Vertex parentItem = items[parentIndex];
                    while (currentItem.compareTo(parentItem) == -1) {
                        swap(currentIndex, parentIndex);
                        currentIndex = parentIndex;
                        currentItem = items[currentIndex];
                        parentIndex = (currentIndex-1) / 2;
                        parentItem = items[parentIndex];
                    }
                }
            }

            public void add(Vertex item) {
                items[size] = item;
                heapifyAfterAdd();
                size++;
            }

            private void swap(int index1, int index2) {
                Vertex temp = items[index1];
                items[index1] = items[index2];
                items[index2] = temp;
            }

            private void heapifyAfterAdd() {
                int currIndex = size;
                Vertex currItem = items[currIndex];
                int parentIndex = currIndex / 2;
                Vertex parentItem = items[parentIndex];
                while (currItem.compareTo(parentItem) == -1) {
                    swap(parentIndex, currIndex);
                    currIndex = parentIndex;
                    currItem = items[currIndex];
                    parentIndex = currIndex / 2;
                    parentItem = items[parentIndex];
                }
            }

            public Vertex remove() {
                return remove(0);
            }

            public Vertex remove(Vertex vertex) {
                int i = 0;
                for (; i < size; i++) {
                    if (items[i] == vertex) {
                        break;
                    }
                }
                if (i < size) {
                    return remove(i);
                }
                return null;

            }

            private Vertex remove(int index) {
                Vertex vertex = items[index];
                swap(index, size - 1);
                items[size - 1] = null;
                size--;
                heapifyAfterRemove(index);
                return vertex;
            }

            private void heapifyAfterRemove(int index) {
                int currIndex = index;
                Vertex currItem = items[currIndex];
                int childIndex;
                Vertex childItem;
                int left = 2 * currIndex + 1;
                int right = 2 * currIndex + 2;
                if (left > size - 1) {
                    return;
                }
                if (right > size - 1) {
                    childIndex = left;
                } else if (items[left].compareTo(items[right]) == -1) {
                    childIndex = left;
                } else {
                    childIndex = right;
                }
                childItem = items[childIndex];

                while (childItem.compareTo(currItem) == -1) {
                    swap(currIndex, childIndex);
                    currIndex = childIndex;
                    currItem = items[currIndex];
                    left = 2 * currIndex + 1;
                    right = 2 * currIndex + 2;
                    if (left > size - 1) {
                        return;
                    }
                    if (right > size - 1) {
                        childIndex = left;
                    } else if (items[left].compareTo(items[right]) == -1) {
                        childIndex = left;
                    } else {
                        childIndex = right;
                    }
                    childItem = items[childIndex];
                }
            }

            public boolean isEmpty() {
                return size == 0;
            }
        }

        public static class HashMap {
            private MapNode[] map;
            private char[] keySet;
            private int maxSize;
            private int size;

            public HashMap(int maxSize) {
                this.maxSize = maxSize;
                map = new MapNode[maxSize];
                keySet = new char[maxSize];
            }

            private static class MapNode {
                char key;
                int value;
                MapNode next;

                public MapNode(char key, int value, MapNode next) {
                    this.key = key;
                    this.value = value;
                    this.next = next;
                }
            }

            public int hash(char key) {
                return 31 * key;
            }

            public int getmapIndexOfkey(char key) {
                return hash(key) % maxSize;
            }

            public void put(char key, int value) {
                int index = getmapIndexOfkey(key);
                map[index] = new MapNode(key, value, map[index]);
                keySet[index] = key;
                size++;
            }

            public int get(char key) {
                int index = getmapIndexOfkey(key);
                MapNode temp = map[index];
                while (temp != null) {
                    if (temp.key == key) {
                        break;
                    }
                }
                if (temp != null) {
                    return temp.value;
                } else {
                    return -1;
                }
            }

            public char[] keyset() {
                return keySet;
            }
        }

        public static class Vertex {
            public static final int NEW = 0;
            public static final int IN_Q = 1;
            public static final int VISITED = 2;
            private int state = NEW;
            private int cost = Integer.MAX_VALUE;
            private char data;
            private Neighbour adj;
            private int index;
            private int parentIndex = -1;

            public int compareTo(Vertex other) {
                if (cost < other.cost) {
                    return -1;
                }
                if (cost > other.cost) {
                    return 1;
                }
                return 0;
            }

            public Vertex(char data, int index) {
                this.data = data;
                this.index = index;
            }

            public void addAdjacentVertex(Neighbour adj) {
                this.adj = adj;
            }

            public void updateCost(int newCost, int parentIndex) {
                this.cost = newCost;
                this.parentIndex = parentIndex;
            }
        }

        public static class Neighbour {
            private Neighbour next;
            private int index;
            private int weight;

            public Neighbour(int index, int weight, Neighbour next) {
                this.next = next;
                this.index = index;
                this.weight = weight;
            }
        }
    }
}