最小生成树问题 贪心算法

最小生成树问题是指在一个加权连通图中找到一棵生成树，使得树上所有边的权值之和最小。其中，贪心算法是求解最小生成树问题的一种常用算法。

在Python中，可以使用Prim算法或Kruskal算法来实现最小生成树问题的求解。其中，Prim算法是一种基于点的贪心算法，而Kruskal算法是一种基于边的贪心算法。

下面是Prim算法的实现代码：

def prim(graph, start):
    """
    Prim算法实现最小生成树
    :param graph: 图
    :param start: 起始节点
    :return: 最小生成树
    """
    # 初始化
    visited = set()
    visited.add(start)
    edges = []
    min_tree = []
    for edge in graph[start]:
        edges.append(edge)
    # 贪心选择
    while edges:
        # 选择最小边
        min_edge = min(edges, key=lambda x: x[2])
        edges.remove(min_edge)
        # 判断是否形成环
        if min_edge[1] not in visited:
            visited.add(min_edge[1])
            min_tree.append(min_edge)
            # 更新可选边
            for edge in graph[min_edge[1]]:
                if edge[1] not in visited:
                    edges.append(edge)
    return min_tree

上述代码中，graph表示图的邻接表表示，start表示起始节点。在算法实现中，首先初始化visited集合和edges列表，visited集合用于记录已经访问过的节点，edges列表用于记录可选边。然后，通过贪心选择，选择最小边，并判断是否形成环，如果没有形成环，则将该边加入最小生成树中，并更新可选边。最后，返回最小生成树。