Big-O of Kruskal/Prim Algorithm

Question

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())[0]
 visited.add(starting_vertex)
 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
 visited.add(to)
 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.

Answer 1

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.

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