**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.

**Table of Contents**

### 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.

```
#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):
self.nodes.append(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`

.

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
else:
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
else:
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.

```
#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
self.MST.append([s,d,w])
ds.union(x,y)
self.printSolution(s,d,w)
g = Graph(5)
g.addNode("A")
g.addNode("B")
g.addNode("C")
g.addNode("D")
g.addNode("E")
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)
g.kruskalAlgo()
```

**Output**

#### 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.

```
#Function to implement Prim's Algorithm
def primsAlgo(self):
visited = [0]*self.vertexNum
edgeNum=0
visited[0]=True
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
self.printSolution()
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)
g.primsAlgo()
```

**Output**

#### 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 Algorithm | Prim’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. |

Applications– Landing Cables – TV Network – Tour Operations – LAN Network | Applications– Cluster Analysis -Travelling Salesman Problem – Network for roads and rail tracks – Designing fiber optics grid |