What is Minimum Spanning Tree?

Given a connected and undirected graph, a spanning tree of that graph is a subgraph that is a tree and connects all the vertices together. A single graph can have many different spanning trees. A minimum spanning tree (MST) or minimum weight spanning tree for a weighted, connected and undirected graph is a spanning tree with weight less than or equal to the weight of every other spanning tree. The weight of a spanning tree is the sum of weights given to each edge of the spanning tree.

Kruskal’s Minimum Spanning Tree

Algorithm

1. Sort all the edges in non-decreasing order of their weight.
2. Pick the smallest edge. Check if it forms a cycle with the spanning tree 
	 formed so far. If cycle is not formed, include this edge. Else, discard it.
3. Repeat step#2 until there are (V-1) edges in the spanning tree.

Implementation

List<Edge<Integer>> findKruskalsMinimumSpanningTree(WeightedGraph<Integer> graph) {
    List<Edge<Integer>> allEdges = graph.getAllEdges();
    allEdges.sort((a, b) -> a.getWeight() - b.getWeight());
    DisjointSet disjointSet = new DisjointSet();
    graph.getGraphNodes().forEach(graphNode -> disjointSet.makeSet(graphNode.getVal())); //TODO should be get id

    List<Edge<Integer>> result = new ArrayList<>();
    for (Edge<Integer> edge : allEdges) {
        GraphNode<Integer> src = edge.getSrc();
        GraphNode<Integer> dst = edge.getDest();
        if (disjointSet.union(src.getVal(), dst.getVal())) {
            result.add(edge);
        }
    }
    return result;
}

Time complexity

O(ElogE + E)

Space Complexity

O(V + E)