0

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
Improve this question

1 Answer 1

Reset to default
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))
Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

Sorry lack of sleep and I made many careless errors I have updated the block fixing those issues, and attempted to make it more clear I imported the py that has the enqueue method as pq. Afterupdating I now have an infinite loop
what's your dequeue method
Updating block for dequeue
That fixed most of the issues it works starting at the first vertex, and leaves off one branch of the minimal spanning tree so it mostly works, but fails for starting at vertex 3. So, there's some more errors somewhere that i'm not seeing at the moment. Thank you for all your help for helping me get this far
It is also a good idea to accept and/or upvote the answers that help you (I can see in your profile that you didn't accept any answers yet, but seems like people helped you multiple times already, so I would encourage to accept those as well)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.