# Big-O of Kruskal/Prim Algorithm

I made simple Kruskal/Prim algorithm with a graph constructed by nested Python dictionary.

Kruskal

parent = {}
rank = {}

def find(v):
if parent[v] != v:
parent[v] = find(parent[v])

return parent[v]

def union(v, u):
root1 = find(v)
root2 = find(u)

if rank[root1] > rank[root2]:
parent[root2] = root1
else:
parent[root1] = root2
if rank[root1] == rank[root2]:
rank[root2] += 1

def kruskal(graph):
for v in graph.keys():
parent[v] = v
rank[v] = 0

edges = []
mst = []

for outer_key in graph.keys():
for inner_key, inner_weight in graph[outer_key].items():
edges.append((inner_weight, outer_key, inner_key))

edges.sort()

for edge in edges:
weight, v, u = edge

if find(v) != find(u):
union(v, u)
mst.append(edge)

return mst

if __name__ == '__main__':
arg_graph = {
'A': {'B': 10, 'D': 5},
'B': {'A': 10, 'C': 2, 'D': 7, 'E': 12},
'C': {'B': 2, 'E': 11, 'F': 14},
'D': {'A': 5, 'B': 7, 'E': 6, 'G': 9},
'E': {'B': 12, 'C': 11, 'D': 6, 'F': 15},
'F': {'C': 14, 'E': 15, 'G': 3},
'G': {'D': 9, 'F': 3}
}

print(kruskal(arg_graph))


Prim

import queue

def prim(graph):
que = queue.PriorityQueue()
mst = []
visited = set()

starting_vertex = list(graph.keys())

for next_to, weight in graph[starting_vertex].items():
que.put((weight, starting_vertex, next_to))

while que.empty() is False:
edge = que.get()
weight, frm, to = edge

if to in visited:
continue

mst.append(edge)

for next_to, weight in graph[to].items():
if next_to not in visited:
que.put((weight, to, next_to))

return mst

if __name__ == '__main__':
arg_graph = {
'A': {'B': 10, 'D': 5},
'B': {'A': 10, 'C': 2, 'D': 7, 'E': 12},
'C': {'B': 2, 'E': 11, 'F': 14},
'D': {'A': 5, 'B': 7, 'E': 6, 'G': 9},
'E': {'B': 12, 'C': 11, 'D': 6, 'F': 15},
'F': {'C': 14, 'E': 15, 'G': 3},
'G': {'D': 9, 'F': 3}
}

print(prim(arg_graph))


With this algorithm, minimun spanning tree is made like this:

"""
10         2                                   2
[A]--------[B]-------[C]            [A]        [B]-------[C]
|    7   / |   11  / |              |    7   /
5 | +-----+ 12  +---+  | 14         5 | +-----+
|/         | /       |              |/
[D]--------[E]-------[F]    ===>    [D]--------[E]       [F]
|     6         15   |              |     6              |
+----+           +---+              +----+           +---+
9 |           | 3                   9 |           | 3
+----[G]----+                       +----[G]----+

(Minimum Spanning Tree)
"""


People says time complexity of Kruskal's Algorithm is $$\O(ElogE)\$$ and Prim's Algorithm is $$\O(ElogV)\$$. (E = number of edges, V = nubmer of vertices)

Then, does my code also have same complexity?

My Kruskal's Algorithm seems have $$\O(V^2)\$$ because of nested for-loop, and I can't figure out how complex my Prim's Algorithm is.

def kruskal(graph):
for v in graph.keys():      # <- O(V)
parent[v] = v
rank[v] = 0

edges = []
mst = []

# this for loop creates a list of all edges O(E)
for outer_key in graph.keys():
for inner_key, inner_weight in graph[outer_key].items():
edges.append((inner_weight, outer_key, inner_key))

edges.sort()    # <- this is O(ElogE) and where the complexity comes from

for edge in edges:
weight, v, u = edge

if find(v) != find(u):
union(v, u)           # <- union-find, let's check this in a second
mst.append(edge)
# ... so the whole for loop is O(E*O(union))
return mst



So, your overall complexity is O(ElogE + E*O(union))

Let's look at your union-find implementation:

def find(v):   # find with path compression
if parent[v] != v:
parent[v] = find(parent[v])

return parent[v]

def union(v, u):    # union by rank
root1 = find(v)
root2 = find(u)

if rank[root1] > rank[root2]:
parent[root2] = root1
else:
parent[root1] = root2
if rank[root1] == rank[root2]:
rank[root2] += 1


According to Wikipedia, this implementation is in O(inverse Ackermann(n)), so that means for the overall implementation we get

O(ElogE), which is purely driven by the sort, or as Wikipedia says

O(T_sort(E) + E*(inverse Ackermann(V)))

In other words, your kruskal algorithm is fine complexity-wise.

Your Prims algorithm is O(ElogE), the main driver here is the PriorityQueue. Notice that your loop will be called O(E) times, and the inner loop will only be called O(E) times in total. So the main driver is adding and retriveving stuff from the Priority Queue. The operations on the PriorityQueue are in O(logE), so O(ElogE) in total for the whole loop.

• Does O(union) mean total complexity of union()? – EnDelt64 Aug 13 '19 at 15:24
• @NBlizz I meant one execution of union(), E*O(union) because it is executed for every edge at most once. – kutschkem Aug 13 '19 at 15:41