python - Prim 算法无法生成正确的生成树

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

我正在用 Python 制作非常简单的 Prim 算法。在此代码中，图形是使用嵌套字典制作的。我将所有边(元组)插入优先级队列，从中一一获取它们，检查是否是已访问的顶点，并将相邻顶点插入优先级队列。

然而，最终生成树的形状是这样的:

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

我想知道问题出在哪里以及如何解决。谢谢。

Answer 1

Prim 的算法从任意顶点开始。然后它将所有边添加到优先级队列并开始循环。

您将所有边添加到队列中(也许您与 Kruskal 混淆了，Kruskal 还执行其他操作)。

工作代码是这样的:

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