生成最小生成树的python代码

以下是基于Prim算法的Python代码，用于生成最小生成树：

import heapq

def prim(graph):
    """
    :param graph: 二维邻接矩阵，表示图
    :return: 最小生成树
    """
    n = len(graph)
    visited = [False] * n
    edges = []
    # 从第一个节点开始
    visited[0] = True
    # 初始化堆
    heap = [(graph[0][j], 0, j) for j in range(1, n)]
    heapq.heapify(heap)
    while heap:
        weight, u, v = heapq.heappop(heap)
        if visited[v]:
            continue
        visited[v] = True
        edges.append((u, v, weight))
        # 将新遍历到的节点的边加入堆中
        for j in range(n):
            if not visited[j]:
                heapq.heappush(heap, (graph[v][j], v, j))
    return edges

该算法的时间复杂度为O(ElogV)，其中E为边数，V为节点数。

相关问题

最小生成树python代码

以下是Prim算法和Kruskal算法的Python代码实现，用于求解图的最小生成树：

# Prim算法
def prim(graph):
    # 初始化
    visited = set()
    unvisited = set(graph.keys())
    start = unvisited.pop()
    visited.add(start)
    heap = [(cost, start, end) for end, cost in graph[start].items()]
    heapq.heapify(heap)
    # 循环直到所有节点都被访问
    while unvisited:
        cost, start, end = heapq.heappop(heap)
        if end in visited:
            continue
        visited.add(end)
        unvisited.remove(end)
        for next_end, next_cost in graph[end].items():
            if next_end not in visited:
                heapq.heappush(heap, (next_cost, end, next_end))
    return visited

# Kruskal算法
def kruskal(graph):
    # 初始化
    edges = []
    for start, ends in graph.items():
        for end, cost in ends.items():
            edges.append((cost, start, end))
    edges.sort()
    parents = {node: node for node in graph.keys()}
    # 循环直到所有边都被访问
    for cost, start, end in edges:
        if find(parents, start) != find(parents, end):
            union(parents, start, end)
    return parents

def find(parents, node):
    if parents[node] != node:
        parents[node] = find(parents, parents[node])
    return parents[node]

def union(parents, node1, node2):
    parents[find(parents, node1)] = find(parents, node2)

最小生成树算法python代码

下面是使用 Prim 算法实现最小生成树的 Python 代码：

INF = float('inf')

def prim(graph):
    n = len(graph)
    selected = [False] * n
    dist = [INF] * n
    dist[0] = 0

    for _ in range(n):
        u = -1
        for i in range(n):
            if not selected[i] and (u == -1 or dist[i] < dist[u]):
                u = i
        selected[u] = True
        for v, w in graph[u]:
            if not selected[v] and w < dist[v]:
                dist[v] = w

    return sum(dist)

# 测试
graph = [
    [(1, 5), (2, 1)],
    [(0, 5), (2, 2), (3, 1)],
    [(0, 1), (1, 2), (3, 4)],
    [(1, 1), (2, 4)]
]
print(prim(graph)) # 输出 5

上述代码中，`graph` 是一个邻接表表示的图，其中 `graph[i]` 是一个列表，表示顶点 `i` 的邻居，列表中每个元素是一个二元组 `(v, w)`，表示顶点 `i` 与顶点 `v` 之间有一条权重为 `w` 的边。`prim` 函数返回最小生成树的权重和。