<aside> 🌲

Kruskal's Algorithm:

• Set an empty set A={} and F = E where E is the set of all edges.
• Choose an edge e in F of minimum weight, and check whether adding e to A creates a cycle
  • If it does, remove e from F
  • If it doesn't, move e from F to A
• If F={} stop and output the minimal spanning tree (V,A). </aside>

What are greedy algorithms and why is the Kruskal's Algorithm greedy?

A greedy algorithm is a simple, intuitive algorithm that is used in optimization problems. The algorithm makes the optimal choice at each step as it attempts to find the overall optimal way to solve the entire problem. Greedy algorithms are quite successful in some problems, such as Huffman encoding which is used to compress data, or Dijkstra's algorithm, which is used to find the shortest path through a graph. (Source: Brilliant.org)

Greedy algorithms are also used as exploration policies in reinforcement learning. A greedy exploration will most of the time choose the best way to solve an optimization problem locally, but will also keep track of the global situation and try to solve our problem globally. This can be easily visualized in finding shortest paths algorithms. See CSC311 Assignment 3 for a nice reinforcement learning implementation using greedy policy with a lot of visualization. A3

In Kruskal's Algorithm the greedy policy can easily be seen. Here we make a series of decisions, each doing what seems best at the time. The local decisions are which edge to add to the spanning tree formed. In each case, we pick the edge with the least weight that does not violate the definition of a spanning tree by completing a cycle. Most of time the overall effect of a locally optimal solution is not globally optimal. However in Kruskal's algorithm the optimal local solution lead to a global optimal solution due the nature of our object.

A simple python Implementation of the Kruskal's Algorithm to find the smallest Minimum Spanning Tree in a Graph:

from typing import List

# Create the Edge object
class Edge:
    def __init__(self, arg_src: int, arg_dst: int, arg_weight: int):
        self.src = arg_src
        self.dst = arg_dst
        self.weight = arg_weight

#Create the Graph object
class Graph:
    def __init__(self, num_nodes: int, edgelist: List[Edge]):
        self.num_nodes = num_nodes
        self.edgelist = edgelist
        self.parent = []
        self.rank = []
        # mst stores edges of the minimum spanning tree
        self.mst = []
		
		#Function that finds the parent of a given node
    def FindParent(self, node: int):
        if node != self.parent[node]:
            self.parent[node] = self.FindParent(self.parent[node])
        return self.parent[node]
		
		#**Kruskal's MST Algorithm**
    def KruskalMST(self):

        # Sort objects of an Edge class based on attribute (weight)
        self.edgelist.sort(key=lambda Edge: Edge.weight)

        self.parent = [None] * self.num_nodes
        self.rank = [None] * self.num_nodes

        for n in range(self.num_nodes):
            # Every node is the parent of itself at the beginning
            self.parent[n] = n
            self.rank[n] = 0   # Rank of every node is 0 at the beginning

        for edge in self.edgelist:
            root1 = self.FindParent(edge.src)
            root2 = self.FindParent(edge.dst)

            # Parents of the source and destination nodes are not in the same subset
            # Add the edge to the spanning tree
            if root1 != root2:
                self.mst.append(edge)
                if self.rank[root1] < self.rank[root2]:
                    self.parent[root1] = root2
                    self.rank[root2] += 1
                else:
                    self.parent[root2] = root1
                    self.rank[root1] += 1

        #
        print("\\nEdges of minimum spanning tree in graph :", end=' ')
        cost = 0
        for edge in self.mst:
            print(str(edge.src) + "---(" + str(edge.weight) + ")---" +
                  str(edge.dst), end=' / ')
            cost += edge.weight
        print("\\nCost of minimum spanning tree : " + str(cost))

Output of some test cases:

Edges of minimum spanning tree in graph : 0---(1)---2 / 3---(1)---4 / 1---(2)---3 / 
2---(2)---3 / 1---(3)---5 / 
Cost of minimum spanning tree : 9

Edges of minimum spanning tree in graph : 0---(1)---1 / 0---(1)---3 / 0---(1)---4 
/ 0---(1)---6 / 2---(1)---3 / 5---(1)---6 /
Cost of minimum spanning tree : 6