[Python]贪心算法-Prim-和-Kruskal实现-最小生成树

标签：pen   python实现   node   cte   ==   nio   geeks   star   connect   

目标

在连通网的所有生成树中，找到所有边的代价和最小的生成树，简称最小生成树问题.
(简要的来说，就是在AOV网中找出串联n个顶点代价总和最小的边集)

下面记录最小生成树的两种算法，Prim和Kruskal

Prim算法思路

1. 从任意一个顶点开始，每次选择与当前顶点最近的一个顶点，并将两点之间的边加入到树中
2. 被选中的点构成一个集合，剩下的点是候选集
3. 每次从已选择的点的集合中，查找花费最小的点，加入进来
4. 同时在候选集中删去，
5. 重复3和4，知道候选集中没有元素。

Prim算法代码

def cmp(key1, key2):
    return (key1, key2) if key1  0:
        edge_dict = dict()
        for node in visited:  # find all visited nodes
            for connected_node, weight in graph[node].items():  # find those were connected
                if connected_node in candidate:
                    edge_dict[cmp(connected_node, node)] = weight
        edge, cost = sorted(edge_dict.items(), key=lambda kv: kv[1])[0]  # find the minimum cost edge
        tree.append(edge)
        visited.add(edge[0])  # cause you dont know which node will be put in the first place
        visited.add(edge[1])
        candidate.discard(edge[0]) # same reason. discard wont raise an exception.
        candidate.discard(edge[1])
    return tree


if __name__ == ‘__main__‘:
    graph_dict = {
        "A": {"B": 7, "D": 5},
        "B": {"A": 7, "C": 8, "D": 9, "E": 5},
        "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}
    }

    path = prim(graph_dict, "D")
    print(path)  # [(‘A‘, ‘D‘), (‘D‘, ‘F‘), (‘A‘, ‘B‘), (‘B‘, ‘E‘), (‘C‘, ‘E‘), (‘E‘, ‘G‘)]

与Prim算法关注图的点不同，Kruskal算法更关注图中的边。

Kruskal算法思路

1. 首先对图中所有的边进行递增排序，排序标准是每条边的权值
2. 依次遍历每条边，如果这条边加进去之后，不会使图形成环，那就加进去，否则放弃

Kruskal算法虽然看起来思路清晰，但是如何判断图中是否成环，比较难理解。

Kruskal算法代码

def cmp(key1, key2):
    return (key1, key2) if key1 

参考文章

1. 图遍历算法之最小生成树Prim算法与 Kruskal算法)
2. 图论（6）：图的最小生成树问题 - Prim和Kruskal算法
3. 判断成环
4. 谈谈Kruskal与Prim这两种最小生成树算法（Python实现）

[Python]贪心算法-Prim-和-Kruskal实现-最小生成树

标签：pen   python实现   node   cte   ==   nio   geeks   star   connect   

原文地址：https://www.cnblogs.com/sight-tech/p/13197982.html