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算法和kruskal算法生成最小生成树

好的，我来为您解答这个问题。

首先，Prim算法和Kruskal算法都是用来生成最小生成树的算法，它们的基本思想都是贪心算法。

下面分别介绍Prim算法和Kruskal算法的实现方法。

1. Prim算法

Prim算法的基本思想是从任意一点开始，不断选择与当前生成树相邻的最短边，直到生成一棵包含所有点的最小生成树。

下面是Prim算法的Python实现：

def prim(graph):
    # 初始化节点集合、边集合和已访问的节点集合
    nodes = set(graph.keys())
    edges = []
    visited = set()

    # 从任意一个节点开始
    current_node = nodes.pop()
    visited.add(current_node)

    # 对每个节点进行遍历
    while nodes:
        # 获取当前节点相邻的边集合
        adjacent_edges = [(weight, current_node, node) for node, weight in graph[current_node].items() if node in nodes]
        # 选择最短的边
        weight, from_node, to_node = sorted(adjacent_edges)[0]
        # 将边添加到边集合中
        edges.append((from_node, to_node, weight))
        # 将当前节点添加到已访问的节点集合中
        visited.add(to_node)
        # 将当前节点设置为新的节点
        current_node = to_node
        # 从节点集合中删除已经访问过的节点
        nodes.discard(current_node)

    return edges

2. Kruskal算法

Kruskal算法的基本思想是将所有边按照权重从小到大排序，然后依次加入生成树中，如果加入后形成环，则不加入。

下面是Kruskal算法的Python实现：

def kruskal(graph):
    # 初始化节点集合、边集合和并查集
    nodes = set(graph.keys())
    edges = []
    disjoint_set = {node: {node} for node in nodes}

    # 将所有边按照权重排序
    sorted_edges = sorted([(weight, from_node, to_node) for from_node, adjacent_nodes in graph.items() for to_node, weight in adjacent_nodes.items()])

    # 遍历所有边
    for weight, from_node, to_node in sorted_edges:
        # 判断边的两个端点是否已经在同一个集合中
        if disjoint_set[from_node] & disjoint_set[to_node]:
            continue
        # 将边添加到边集合中
        edges.append((from_node, to_node, weight))
        # 合并两个集合
        disjoint_set[from_node] |= disjoint_set[to_node]
        disjoint_set[to_node] = disjoint_set[from_node]

    return edges

以上就是Prim算法和Kruskal算法的Python实现。希望能对您有所帮助！