Prim's Algorithm doesn't make proper spanning tree

Question

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

    # Generate edge information with tuple and push it to Priority Queue
    for outer_key in graph.keys():
        for inner_key, inner_cost in graph[outer_key].items():
            que.put((inner_cost, outer_key, inner_key))

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

        if to in visited:
            continue

        visited.add(frm)
        visited.add(to)
        mst.append(edge)

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

    return mst

Full source code

I'm making very simple Prim's Algorithm with Python. In this code, graph is made with nested dictionary. I pushed all edges(tuple) to Priority Queue, get them one by one from it, check whether is it a visited vertex, and pushed adjacent vertex to Priority Queue.

However, the shape of final spanning tree is like this:

                   2
  [A]        [B]-------[C]
   |
 5 |
   |
  [D]--------[E]       [F]
         6              |
                    +---+
                    | 3
             [G]----+

I want to know where the problem is and how to fix it. Thanks.

Itay · Accepted Answer · 2019-08-12 15:27:31Z

Prim's algorithm starts from an arbitrary vertex. It then adds all its edges to the priority queue and starts the loop.

You added all the edges to the queue (maybe you got confused with Kruskal which does something else).

A working code is hence:

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

    # Generate edge information with tuple and push it to Priority Queue
    #for outer_key in graph.keys():
    #    for inner_key, inner_cost in graph[outer_key].items():
    #        que.put((inner_cost, outer_key, inner_key))

    starting_vertex = list(graph.keys())[0]

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

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

        if to in visited:
            continue

        visited.add(frm)
        visited.add(to)
        mst.append(edge)

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

    return mst

Collectives™ on Stack Overflow

Prim's Algorithm doesn't make proper spanning tree

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related