CODEWITHSUNDEEP
python
EnDelt64
EnDelt64

Reputation: 1360

Prim's Algorithm doesn't make proper spanning tree

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.

Upvotes: 1

Views: 262

Answers (1)

Itay
Itay

Reputation: 16777

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

Upvotes: 1

Related Questions