最小生成树贪心法python代码实例

在Python中，我们可以使用Prim's算法或Kruskal算法实现最小生成树的贪心方法。这里以Prim's算法为例给出一个简单的实现：

import heapq

def prim(graph):
    # 初始化
    vertices = set(range(len(graph)))
    minHeap = []
    for node in graph:
        if node[0] not in vertices:
            heapq.heappush(minHeap, (node[0], node[1]))

    # 边集合
    edges_added = set()

    while minHeap:
        # 弹出当前最小边
        current_edge = heapq.heappop(minHeap)
        u, weight = current_edge
        vertices.remove(u)

        # 如果u已经被访问过，跳过这条边
        if u not in edges_added:
            for v, w in graph[u]:
                if v not in vertices and (v, w) not in edges_added:
                    heapq.heappush(minHeap, (v, w))
                    edges_added.add((u, v))

    return edges_added

# 示例图，邻接矩阵表示
graph = [
    [(0, 4), (1, 8)],
    [(0, 7), (1, 1)], 
    [(1, 4), (2, 8)],
    [(2, 8), (3, 7)],
    [(3, 9)],
]

print("Minimum spanning tree using Prim's algorithm:", prim(graph))

在这个例子中，我们首先创建一个优先队列（minHeap），然后遍历每个节点和它的邻居，只考虑未加入边集的那些。每次弹出最小边并更新边集，直到所有节点都被访问过。最终返回的就是最小生成树的边集合。