prim's algorithm in python

Question

I've looked through the questions on this already and still having some trouble. What exactly is going wrong in my attempt to implement Prim's algorithm? I feel like it is something to do with it not adding it to the spanning tree only if it is the minimum weight in the tree, but I'm failing to see how to implement this. Here is what I have tried so far and i will include the priority queues enqueue method at the top. It appears to add all of the vertices to the tree. The output I get for starting at the vertex 0 is the following..

(0, 5), (1, 5), (2, 5), (3, 5), (4, 5), (5, 5), (0, 1), (1, 1), (2, 1), (3, 1) (4, 1), (0, 2), (2, 2), (3, 2), (4, 2), (0, 4), (3, 4), (4, 4)

 def dequeue(self):
    weight, data = self.queue.pop(0)
    self.size -= 1
    return data

 def enqueue(self, data, weight):
    curr_index = 0

    while (curr_index < self.size and
           self.queue[curr_index][WEIGHT] < weight):
        curr_index += 1

    self.queue.insert(curr_index, (weight, data))
    self.size += 1

def add_edges(self, p_queue, vertex, vertices):
    for i in range(len(self.adjacency_matrix)):
        weight = self.adjacency_matrix[vertex][i]
        if weight != 0:
            p_queue.enqueue(vertex, weight)
            if (i, vertex) not in vertices:
                vertices.append((i, vertex))
    return vertices 


def init_pqu(self, p_queue, start_vertex):
    for i in range(len(self.adjacency_matrix)):
        weight = self.adjacency_matrix[start_vertex][i]
        if weight != 0:
            p_queue.enqueue(start_vertex, weight)


def prim(self, start_vertex):
    vertices = []
    priority_queue = pq.priority_queue()
    self.init_pqu(priority_queue, start_vertex)
    while len(priority_queue.queue) > 0:
        source = priority_queue.dequeue()
        vertices = self.add_edges(priority_queue, source, vertices)
    return vertices

Answer 1

There are multiple issues with your code, that I can immediately spot:

1) It is not clear if the enqueue method you provided is the same as the pq.enqueue you are calling. If it is the same, then your enqueue takes two arguments (vertex and weight), but you only pass it the vertex, so the weight is always passed as None, making the priority queue returning you random vertex every time.

If it is not the same, then first of all you never call your enqueue, you always call pq.enqueue, second of all, you insert vertex ids into your priority queue, so it is sorted by the vertex id, not by the weight of the edge. It is crucial for the Prima algorithm that the priority queue ordered by the weights.

2) This code is also incorrect:

    if (vertex, i) not in vertices:
        vertices.append((i, vertex))

Because you check for (vertex, i), but append (i, vertex), so your condition will either never trigger, or trigger in a wrong way.

3) Your add_edges routine has an argument p_queue, but uses pq instead. Is pq some kind of global priority queue you have?

UPDATE: after all these were fixed, now also only add a vertex to the queue if it was not added before, so in other words instead of doing this:

        p_queue.enqueue(vertex, weight)
        if (i, vertex) not in vertices:
            vertices.append((i, vertex))

Do this:

        if (i, vertex) not in vertices:
            p_queue.enqueue(vertex, weight)
            vertices.append((i, vertex))