Kruskal and Prim’s Algorithm in Python

Kruskals And Prms Algorithm Python Feature

Kruskal’s Algorithm and Prim’s Algorithm are “minimum spanning tree” algorithms. For the implementation of these algorithms, we must have adequate knowledge of Graphs and Disjoint set data structures. Hence, before moving on to the algorithms, we define the necessary data structures.

Creation of Graph

To implement the Graph data structure, we first initialize the “Graph” class. Then, we overwrite the __init__ function and create another function to add weighted edges between the newly added nodes.

Image 253
#Initializing the Graph Class
class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = []
        self.nodes = []
        self.MST = []

    def addEdge(self, s, d, w):
        self.graph.append([s, d, w])
    def addNode(self, value):

    def printSolution(self,s,d,w):
        for s, d, w in self.MST:
            print("%s - %s: %s" % (s, d, w))

Creation of Disjoint Set

To implement the disjoint set data structure, we first create the DisjointSet class and overwrite the __init__ function. The init function contains two variables – vertices and a dictionary called parent.

Image 256

The find function takes the value to be searched as a parameter. If the value is found in the disjoint set, the function returns the same.

The union method takes two set elements as parameters. It then merges the two data sets based on the order in which they are passed as arguments.

#Implementing Disjoint Set data structure and its functions
class DisjointSet:
    def __init__(self, vertices):
        self.vertices = vertices
        self.parent = {}
        for v in vertices:
            self.parent[v] = v
        self.rank = dict.fromkeys(vertices, 0)
    def find(self, item):
        if self.parent[item] == item:
            return item
            return self.find(self.parent[item])
    def union(self, x, y):
        xroot = self.find(x)
        yroot = self.find(y)
        if self.rank[xroot] < self.rank[yroot]:
            self.parent[xroot] = yroot
        elif self.rank[xroot] > self.rank[yroot]:
            self.parent[yroot] = xroot
            self.parent[yroot] = xroot
            self.rank[xroot] += 1

Kruskal’s Algorithm in Python

Kruskal’s algorithm is a minimum spanning tree algorithm that takes a graph as input and creates a minimum spanning tree from the subset of that graph. It finds a minimum spanning tree for the weighted undirected graph in the following two ways:

  • Add edges in ascending order of weight at each step.
  • Avoid any cycle formation at each step.

Implementation of Kruskal’s Algorithm

The implementation of Kruskal’s algorithm is based on the following steps:

  • Sort all the edges of the graph from low weight to high.
  • Take the edge of the lowest weight and add it to the required spanning tree. If adding this edge creates a cycle in the graph, then reject this edge.
  • Repeat this process until all the vertices are covered with the edges.
Image 262
#Function to implement Kruskal's Algorithm
def kruskalAlgo(self):
    i, e = 0, 0
    ds = dst.DisjointSet(self.nodes)
    self.graph = sorted(self.graph, key=lambda item: item[2])
    while e < self.V - 1:
        s, d, w = self.graph[i]
        i += 1
        x = ds.find(s)
        y = ds.find(d)
        if x != y:
            e += 1

g = Graph(5)
g.addEdge("A", "B", 5)
g.addEdge("A", "C", 13)
g.addEdge("A", "E", 15)
g.addEdge("B", "A", 5)
g.addEdge("B", "C", 10)
g.addEdge("B", "D", 8)
g.addEdge("C", "A", 13)
g.addEdge("C", "B", 10)
g.addEdge("C", "E", 20)
g.addEdge("C", "D", 6)
g.addEdge("D", "B", 8)
g.addEdge("D", "C", 6)
g.addEdge("E", "A", 15)
g.addEdge("E", "C", 20)



1 24

Time and Space Complexity

The time complexity for Kruskal’s algorithm is O(V + ElogE + EV) where “V” is the number of vertices and “E” is the number of edges in the graph. The space complexity is O(V+E) as we need additional memory to store data elements temporarily.

Prim’s Algorithm in Python

Prim’s algorithm is a minimum spanning tree algorithm that takes a graph as input and creates a minimum spanning tree from the subset of that graph. It finds a minimum spanning tree for the given weighted undirected graph.

Implementation of Prim’s Algorithm

The implementation of Prim’s algorithm is based on the following steps:

  • Take any vertex as the source and set its weight to 0. Set the weights of all other vertices to infinity.
  • For every adjacent vertices, if the current weight is more than that of the current edge, then we replace it with the weight of the current edge.
  • Then, we mark the current vertex as visited.
  • Repeat these steps for all the given vertices in ascending order of weight.
Image 264
#Function to implement Prim's Algorithm
def primsAlgo(self):
    visited = [0]*self.vertexNum
    while edgeNum<self.vertexNum-1:
        min = sys.maxsize
        for i in range(self.vertexNum):
            if visited[i]:
                for j in range(self.vertexNum):
                    if ((not visited[j]) and self.edges[i][j]):
                        if min > self.edges[i][j]:
                            min = self.edges[i][j]
                            s = i
                            d = j
        self.MST.append([self.nodes[s], self.nodes[d], self.edges[s][d]])
        visited[d] = True
        edgeNum += 1

edges = [[0, 10, 20, 0, 0],
		[10, 0, 30, 5, 0],
		[20, 30, 0, 15, 6],
		[0, 5, 15, 0, 8],
		[0, 0, 6, 8, 0]]

nodes = ["A","B","C","D","E"]
g = Graph(5, edges, nodes)


1 25

Time and Space Complexity

The time complexity for Prim’s algorithm is O(V^3) as we use three nested loops, each iterating over the vertices of the graph. The space complexity is O(V) as we need additional memory to store data elements temporarily.

Kruskal vs Prim’s Algorithm

Kruskal’s AlgorithmPrim’s Algorithm
Kruskal’s algorithm concentrates on edges. Prim’s algorithm concentrates on vertices.
Finalizes 1 edge in each iteration. Finalizes 1 vertex edge in each iteration.
– Landing Cables
– TV Network
– Tour Operations
– LAN Network
– Cluster Analysis
-Travelling Salesman Problem
– Network for roads and rail tracks
– Designing fiber optics grid