Hey there!! Now we are heading off to finding a minimal spanning tree for an undirected graph. It is recommended to go through my previous post on Disjoint Set Data Structure
It is assumed that the reader knows about Graph, a very important data structure in computer science with lots of applications(social networks, computer networks, digital circuits, and many more).
An undirected graph has no sense of directions in edges. For example, if we have an edge connecting two vertices A and B, that edge can be called as connecting A to B or B to A. The adjacency matrix for the graph is symmetric.
Above is a simple small graph(hand made by me, no wonder why the graph edges are zig-zagged). The adjacency matrix for the graph is thus,
# the infinity INF = 99999999 # our adjacency matrix adjacency = \ [[INF,7,2,5], [7,INF,4,1], [2,4,INF,4], [5,1,4,INF]]
I have chosen adjacency matrix for graph representation here. And as mentioned earlier, the adjacency matrix is symmetric because it is an undirected graph. INF means infinity and is the weight of the vertices that are not connected. Ignore the blue edges for now.
Kruskal's algorithm goes like this:
- List out the edges of the graph.
- For each edge, make a set containing only the edge. If there are n edges then, there will be n sets(partitions) at this step.
- Take an edge with smallest weight value and check if the vertices connected by it are in same set. If not, union them, else continue with the next smallest edge.
- Repeat till all vertices are contained in a single set.
Lets directly go into the code for the implementation is very very easy.
# number of vertices v = len(adjacency) # now get the edges # an edge is a tuple (vertex 1, vertex 2, weight) edges = [(i, j, adjacency[i][j]) for i in range(v) for j in range(i, v) if adjacency[i][j]!=INF] # sort edges # because we need to take out smallest edges first. edges.sort(key=lambda x: x) # CREATE a disjoint set datastructure # The constructor will automaticall create separate set for each vertex disset = DisjointSet(v) # v is number of vertices c = 0 # counter wts = 0 # total weight of the final spanning treee final_edges =  while c < len(edges): edge = edges[c] i,j, w = edge, edge, edge if disset.find(i) != disset.find(j): wts+=w disset.union(i, j) final_edges.append(edge) c+=1 print(final_edges)
Running the above code for the graph shown above, we get the output:
[(1, 3, 1), (0, 2, 2), (1, 2, 4)] which are the blue edges in the figure.
That's all about the Kruskal's Algorithm. Easy, ain't it??