adamwhiles dot com

Before describing what Kruskals Algorithm is, let’s first explain what a spanning tree and minimum spanning tree are, as these are important concepts to understand.

Imagine a graph like the one above, inside this graph, there are many spanning trees. But what exactly is a spanning tree? A spanning tree is a tree that includes all of the vertices/nodes of the tree but only a subset of the edges you see above. All nodes/vertices must still be connected by edges, creating a connected graph. For it to be a tree, it must not have any cycles in it. Below is an example of a spanning tree within this same graph. The spanning tree below connects all vertices and there are no cycles within it. We also have 6 vertices and to be a spanning tree, the number of edges must be at most n-1. Here we have 5 edges that satisfy this requirement.

Next, we need to understand what a minimum spanning tree is. A minimum spanning tree is a spanning tree for an undirected, connected, but weighted graph. As I said before, a graph can have many possible spanning trees within it, but the minimum spanning tree is the one for which the weights are the least when you add all edges of the spanning tree.

Defining Kruskals Algorithm

Kruskal’s algorithm has the goal of finding the minimum spanning tree for a given weighted, connected, and undirected graph. Below are the steps that Kruskal’s algorithm takes to achieve this.

First, we collect all of the edges in the graph, and sort them by their weights from lowest weight to greatest.

Second, we start with the lowest weight edge. We check that adding this edge to our minimum spanning tree does not create a cycle and if it doesn’t, we add it to our minimum spanning tree. If it creates a cycle, it is thrown out and not included in the MST. The cycle check can be performed using the UNION/FIND method.

We continue going through our sorted list of edges until we reach V-1 vertices in our MST, checking if it will create a cycle and adding it to our MST if it doesn’t.

The resulting MST of this process on the graph I’ve been using as an example would look like the one pictured below.

Is Kruskals Algorithm Greedy?

We are asked what makes Kruskal’s algorithm greedy. By looking at the decisions that the algorithm makes, we can see the answer. It is because the algorithm makes a decision on each iteration to take the lowest cost edge. This choice doesn’t care about the overall big picture, only the cost and the fact that a cycle isn’t created.

Kruskals Algorithm Example in Java

import java.util.*; 

class Node 
{
	private int u;
    private int v;
    private int weight;
    
    Node(int _u, int _v, int _w) { u = _u; v = _v; weight = _w; }
    
    Node() {}
    
    int getV() { return v; }
    int getU() { return u; }
    int getWeight() { return weight; }

}

class SortComparator implements Comparator<Node> {
	@Override
    public int compare(Node node1, Node node2) 
    { 
        if (node1.getWeight() < node2.getWeight()) 
            return -1; 
        if (node1.getWeight() > node2.getWeight()) 
            return 1; 
        return 0; 
   

    } 
} 

class Main
{
	private int findPar(int u, int parent[]) {
		if(u==parent[u]) return u;
		return parent[u] = findPar(parent[u], parent); 
	}
	private void union(int u, int v, int parent[], int rank[]) {
		u = findPar(u, parent); 
		v = findPar(v, parent);
		if(rank[u] < rank[v]) {
        	parent[u] = v;
        }
        else if(rank[v] < rank[u]) {
        	parent[v] = u; 
        }
        else {
        	parent[v] = u;
        	rank[u]++; 
        }
	}
    void KruskalAlgo(ArrayList<Node> adj, int N)
    {
        Collections.sort(adj, new SortComparator());
        int parent[] = new int[N]; 
        int rank[] = new int[N];

        for(int i = 0;i<N;i++) {
        	parent[i] = i; 
        	rank[i] = 0; 
        }

        int costMst = 0;
        ArrayList<Node> mst = new ArrayList<Node>();
        for(Node it: adj) {
        	if(findPar(it.getU(), parent) != findPar(it.getV(), parent)) {
        		costMst += it.getWeight(); 
        		mst.add(it); 
        		union(it.getU(), it.getV(), parent, rank); 
        	}
        } 
        System.out.println(costMst);
        for(Node it: mst) {
        	System.out.println(it.getU() + " - " +it.getV()); 
        }
    }
    public static void main(String args[])
    {
        int n = 5;
        ArrayList<Node> adj = new ArrayList<Node>();
		
			
		adj.add(new Node(0, 1, 2));
		adj.add(new Node(0, 3, 6));
		adj.add(new Node(1, 3, 8));
		adj.add(new Node(1, 2, 3));
		adj.add(new Node(1, 4, 5));
		adj.add(new Node(2, 4, 7));

	
		Main obj = new Main(); 
		obj.KruskalAlgo(adj, n);
		
    }
}

Filed under: Data Structures,Graph Theory - @ October 7, 2022 5:11 pm

Tags: algorithms, data structures, graph theory