2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$
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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.