Execution Time of Prim's

No. of Verticies (n) No. of Edges (m)

Algorithm (in secs)
5 10 0.000018
10 45 0.000088
15 105 0.000159
20 190 0.000365
25 300 0.0007
30 435 0.001242
35 595 0.003339
40 780 0.003975
45 990 0.004099
50 1225 0.004753
55 1485 0.006427
60 1770 0.009677
65 2080 0.015125
70 2415 0.014194
75 2775 0.029004
80 3160 0.021192
85 3570 0.030651
90 4005 0.045322
95 4465 0.091188
100 4950 0.042485

Prim's Algorithm
import time
import random

# Prim's algorithm to find the minimum spanning tree

def prim_algorithm(graph):
num_vertices = len(graph)
visited = [False] * num_vertices
min_spanning_tree = []

# Choose a random starting vertex

start_vertex = random.randint(0, num_vertices - 1)
visited[start_vertex] = True

while len(min_spanning_tree) < num_vertices - 1:

min_edge = None

# Find the minimum weight edge from visited vertices to unvisited vertices
for i in range(num_vertices):
if visited[i]:
for j in range(num_vertices):
if not visited[j] and graph[i][j] != 0:
if min_edge is None or graph[i][j] < graph[min_edge[0]][min_edge[1]]:
min_edge = (i, j)

if min_edge is None:
break

u, v = min_edge
min_spanning_tree.append((u, v))
visited[v] = True

return min_spanning_tree
 Execution Time of
No. of Edges Kruskal's Algorithm (in
Subsets of minimum spanning tree graph
(m) secs)

2 ('0', '1', 1), ('1', '2', 2) 9.46521759033203

3 ('0', '1', 1), ('1', '2', 2), ('2', '3', 3) 0.000120162963867187
4 ('0', '1', 1), ('1', '2', 2), ('2', '3', 3), ('3', '4', 4) 9.87052917480468
0.000135183334350585
5 ('0', '1', 1), ('1', '2', 2), ('2', '3', 3), ('3', '4', 4), ('4', '5', 5)
0.000216007232666015
('0', '1', 1), ('1', '2', 2), ('2', '3', 3), ('3', '4', 4), ('4', '5', 5),
6 ('5', '6', 6)
0.000114202499389648
('0', '1', 1), ('1', '2', 2), ('2', '3', 3), ('3', '4', 4), ('4', '5', 5),
7 ('5', '6', 6), ('6', '7', 7)
0.000134468078613281
('0', '1', 1), ('1', '2', 2), ('2', '3', 3), ('3', '4', 4), ('4', '5', 5),
8 ('5', '6', 6), ('6', '7', 7), ('7', '8', 8)
0.000125885009765625
('0', '1', 1), ('1', '2', 2), ('2', '3', 3), ('3', '4', 4), ('4', '5', 5),
9 ('5', '6', 6), ('6', '7', 7), ('7', '8', 8), ('8', '9', 9)
0.000140666961669921
('0', '1', 1), ('1', '2', 2), ('2', '3', 3), ('3', '4', 4), ('4', '5', 5),
10 ('5', '6', 6), ('6', '7', 7), ('7', '8', 8), ('8', '9', 9), ('9', '10', 10)
0.000212907791137695
('0', '1', 1), ('1', '2', 2), ('2', '3', 3), ('3', '4', 4), ('4', '5', 5),
('5', '6', 6), ('6', '7', 7), ('7', '8', 8), ('8', '9', 9), ('9', '10',
11 10), ('10', '11', 11)
12 ('0', '1', 1), ('1', '2', 2), ('2', '3', 3), ('3', '4', 4), ('4', '5', 5), 0.000396966934204101
13 ('0', '1', 1), ('1', '2', 2), ('2', '3', 3), ('3', '4', 4), ('4', '5', 5), 0.00033879280090332
14 ('0', '1', 1), ('1', '2', 2), ('2', '3', 3), ('3', '4', 4), ('4', '5', 5), 0.000169754028320312
15 ('0', '1', 1), ('1', '2', 2), ('2', '3', 3), ('3', '4', 4), ('4', '5', 5), 0.000257730484008789
16 ('0', '1', 1), ('1', '2', 2), ('2', '3', 3), ('3', '4', 4), ('4', '5', 5), 0.000206470489501953
17 ('0', '1', 1), ('1', '2', 2), ('2', '3', 3), ('3', '4', 4), ('4', '5', 5) 0.000181913375854492
18 ('0', '1', 1), ('1', '2', 2), ('2', '3', 3), ('3', '4', 4), ('4', '5', 5) 0.000144720077514648
19 ('0', '1', 1), ('1', '2', 2), ('2', '3', 3), ('3', '4', 4), ('4', '5', 5) 0.000168323516845703
20 ('0', '1', 1), ('1', '2', 2), ('2', '3', 3), ('3', '4', 4), ('4', '5', 5) 0.00019073486328125
21 ('0', '1', 1), ('1', '2', 2), ('2', '3', 3), ('3', '4', 4), ('4', '5', 5) 0.000258922576904296

Kruskal's Algorithm
import time

class UnionFind:
def __init__(self, vertices):
self.parent = {v: v for v in vertices}
self.rank = {v: 0 for v in vertices}

def find(self, v):

if self.parent[v] != v:
self.parent[v] = self.find(self.parent[v])
return self.parent[v]

def union(self, v1, v2):

root1 = self.find(v1)
root2 = self.find(v2)

if root1 != root2:
if self.rank[root1] < self.rank[root2]:
self.parent[root1] = root2
elif self.rank[root1] > self.rank[root2]:
 Approx.
Execution Time
(In Secs)
9.4652
0.0001
9.8705

0.0001

0.0002

0.0001

0.0001

0.0001

0.0001

0.0002
0.0004
0.0003
0.0002
0.0003
0.0002
0.0002
0.0001
0.0002
0.0002
0.0003
 Execution Time of
Number of Execution Time of Kruskal's
Prims Algorithm (in
Execution Algorithm (in secs) 19
secs) 17
15
1 0.000018 9.4652 13
11
2 0.000088 0.0001
9
3 0.000159 9.8705 7
3 0.000365 0.0001 5
3
4 0.0007 0.0002 1
5 0.001242 0.0001 1 2 3
6 0.003339 0.0001 Number of Execution 1 2 3

7 0.003975 0.0001 Execution Time of Prims Algo- 0.000018 0.000088 0.0001

rithm (in secs)
8 0.004099 0.0001 Execution Time of Kruskal's Al- 9.4652 0.0001 9.870
gorithm (in secs)
9 0.004753 0.0002
10 0.006427 0.0004
11 0.009677 0.0003
12 0.015125 0.0002
13 0.014194 0.0003
14 0.029004 0.0002
15 0.021192 0.0002
16 0.030651 0.0001
17 0.045322 0.0002
18 0.091188 0.0002
19 0.042485 0.0003

Both algorithms have their own advantages. Here are their time complexities.

Kruskal:

O(E lgV) - considering you are using union-by-rank and path-compression heuristics for the disjoint-set forest
implementation.

Prim:

O(E + V lgV) amortized time - using Fibonacci heaps.

O(V^2) - using adjacency matrix.

Now, let us compare the running times. First state them both in terms of vertices. For dense graph, say, E~V^2 :

Kruskal: O((V^2) lgV)

Prim: O(V^2)
So, if you have a dense graph with more edge-to-vertex ratio go for Prim's

else choose Kruskal which performs better for sparse graphs.

Also,
Prim's algorithm requires the graph to be connected
Kruskal, on the other hand, works on disjoint-set data structure, so it functions with disconnected graph as well.
 Number of Execution Execution Time of Prims Algorithm (in secs) Execution Time of Kruskal's Algorithm (in secs)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 2 3 3 4 5 6 7 8 9 10 11 12 13 14
0.000018 0.000088 0.000159 0.000365 0.0007 0.001242 0.003339 0.003975 0.004099 0.004753 0.006427 0.009677 0.015125 0.014194 0.029004 0.0

9.4652 0.0001 9.8705 0.0001 0.0002 0.0001 0.0001 0.0001 0.0001 0.0002 0.0004 0.0003 0.0002 0.0003 0.0002 0

disjoint-set forest

e graph, say, E~V^2 :

nected graph as well.

on Time of Kruskal's Algorithm (in secs)

13 14 15 16 17 18 19 20
12 13 14 15 16 17 18 19
0.015125 0.014194 0.029004 0.021192 0.030651 0.045322 0.091188 0.042485

0.0002 0.0003 0.0002 0.0002 0.0001 0.0002 0.0002 0.0003