python - python中的prim算法

Question

我已经查看了有关此的问题，但仍然遇到一些问题。我在尝试实现 Prim 算法时究竟出了什么问题？我觉得这与它有关，只有当它是树中的最小权重时才将它添加到生成树中，但我看不到如何实现它。到目前为止，这是我尝试过的方法，我将在顶部包含优先级队列入队方法。它似乎将所有顶点添加到树中。我从顶点 0 开始得到的输出如下..

(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

您的代码存在多个问题，我可以立即发现:

1)不清楚你提供的enqueue方法和你调用的pq.enqueue是否一样。如果相同，那么您的队列有两个参数(顶点和权重)，但您只将顶点传递给它，因此权重始终作为 None 传递，使优先级队列每次都返回随机顶点。

如果不一样，那么首先你永远不会调用你的入队，你总是调用pq.enqueue，其次，你插入vertex ids到您的优先级队列，因此它按顶点 ID 排序，而不是按边的权重排序。优先级队列按权重排序对于Prima算法至关重要。

2)这段代码也不正确:

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

因为您检查了 (vertex, i)，但附加了 (i, vertex)，所以您的条件要么永远不会触发，要么以错误的方式触发。

3) 您的 add_edges 例程有一个参数 p_queue，但使用 pq 代替。 pq 是您拥有的某种全局优先级队列吗？

更新:在所有这些都被修复之后，现在也只将一个顶点添加到队列中，如果它之前没有被添加的话，换句话说，而不是这样做:

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

这样做:

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