python实现prim

Prim算法是一种常见的最小生成树算法，可以用来解决带权无向连通图的最小生成树问题。下面是Python实现Prim算法的示例代码：

from queue import PriorityQueue

def prim(graph, start):
    visited = set()
    mst = []
    pq = PriorityQueue()

    visited.add(start)
    for neighbor, weight in graph[start].items():
        pq.put((weight, start, neighbor))

    while not pq.empty():
        weight, u, v = pq.get()
        if v not in visited:
            visited.add(v)
            mst.append((u, v, weight))
            for neighbor, weight in graph[v].items():
                pq.put((weight, v, neighbor))

    return mst

这里使用了优先队列来维护当前候选边集合，以便每次选择权值最小的边进行扩展。同时，使用集合来记录已经访问过的节点，以避免重复扩展。

相关问题

python实现prim算法

Prim算法是一种求解最小生成树的贪心算法，以下是Python实现Prim算法的示例代码：

import heapq

def prim(graph):
    # 初始化
    visited = set()
    mst = []
    start_vertex = list(graph.keys())[0]
    heap = [(0, start_vertex, start_vertex)]
    # 执行Prim算法
    while heap:
        weight, curr_vertex, prev_vertex = heapq.heappop(heap)
        if curr_vertex not in visited:
            visited.add(curr_vertex)
            mst.append((prev_vertex, curr_vertex, weight))
            for neighbor, weight in graph[curr_vertex].items():
                if neighbor not in visited:
                    heapq.heappush(heap, (weight, neighbor, curr_vertex))
    # 返回最小生成树
    return mst

该算法的输入为一个字典类型的图，其中键为顶点，值为另一个字典，表示该顶点与它相邻的顶点以及对应的边权重。例如，对于下图所示的无向图：

A --4-- B
| \    |
2  5   1
|   \  |
D --3-- C

可以用以下代码表示：

graph = {
    'A': {'B': 4, 'D': 2},
    'B': {'A': 4, 'C': 1, 'D': 5},
    'C': {'B': 1, 'D': 3},
    'D': {'A': 2, 'B': 5, 'C': 3}
}

输出为一个列表，表示最小生成树中的所有边和对应的权重。例如，对于上述图，输出为：

[('A', 'D', 2), ('D', 'C', 3), ('C', 'B', 1)]

用python实现prim算法的一个实列

Prim算法是一种求解最小生成树的经典算法，其基本思想是从一个点出发，每次选取与当前生成树距离最近的点加入生成树，直到所有点都被加入生成树。下面是用Python实现Prim算法的代码实例：

#定义Prim算法函数
def Prim(graph):
    nodes = list(graph.keys())
    visited = [nodes]
    unvisited = nodes[1:]
    tree = []
    while unvisited:
        min_weight = float('inf')
        for node_visited in visited:
            for node_unvisited in unvisited:
                if graph[node_visited][node_unvisited] < min_weight:
                    min_weight = graph[node_visited][node_unvisited]
                    edge = (node_visited, node_unvisited)
        tree.append(edge)
        visited.append(edge)
        unvisited.remove(edge)
    return tree

#测试代码
graph = {'A': {'B': 7, 'D': 5},
         'B': {'A': 7, 'C': 8, 'D': 9, 'E': 7},
         'C': {'B': 8, 'E': 5},
         'D': {'A': 5, 'B': 9, 'E': 15, 'F': 6},
         'E': {'B': 7, 'C': 5, 'D': 15, 'F': 8, 'G': 9},
         'F': {'D': 6, 'E': 8, 'G': 11},
         'G': {'E': 9, 'F': 11}}
tree = Prim(graph)
print(tree)

以上代码中，我们定义了一个Prim算法函数，传入一个图（用字典表示），返回一个最小生成树的边集。具体实现过程是：首先选取第一个节点作为已访问节点，将其加入已访问节点集合visited中，其余节点加入未访问节点集合unvisited中。然后在未访问节点集合中寻找与已访问节点集合中距离最近的节点，将它们之间的边加入生成树的边集中。接着将这个新加入的节点加入已访问节点集合中，并从未访问节点集合中删除。循环此过程直到未访问节点集合为空，此时返回生成树的边集即可。