目标
在连通网的所有生成树中，找到所有边的代价和最小的生成树，简称最小生成树问题.
(简要的来说，就是在AOV网中找出串联n个顶点代价总和最小的边集)
下面记录最小生成树的两种算法，Prim和Kruskal
Prim算法思路
- 从任意一个顶点开始，每次选择与当前顶点最近的一个顶点，并将两点之间的边加入到树中
- 被选中的点构成一个集合，剩下的点是候选集
- 每次从已选择的点的集合中，查找花费最小的点，加入进来
- 同时在候选集中删去，
- 重复3和4，知道候选集中没有元素。
Prim算法代码
def cmp(key1, key2):
return (key1, key2) if key1 < key2 else (key2, key1)
def prim(graph, init_node):
visited = {init_node}
candidate = set(graph.keys())
candidate.remove(init_node) # add all nodes into candidate set, except the start node
tree = []
while len(candidate) > 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算法思路
- 首先对图中所有的边进行递增排序，排序标准是每条边的权值
- 依次遍历每条边，如果这条边加进去之后，不会使图形成环，那就加进去，否则放弃
Kruskal算法虽然看起来思路清晰，但是如何判断图中是否成环，比较难理解。
Kruskal算法代码
def cmp(key1, key2):
return (key1, key2) if key1 < key2 else (key2, key1)
def find_parent(record, node):
if record[node] != node:
record[node] = find_parent(record, record[node])
return record[node]
def naive_union(record, edge):
u, v = find_parent(record, edge[0]), find_parent(record, edge[1])
record[u] = v
def kruskal(graph, init_node):
edge_dict = {}
for node in graph.keys():
edge_dict.update({cmp(node, k): v for k, v in graph[node].items()})
sorted_edge = list(sorted(edge_dict.items(), key=lambda kv: kv[1]))
tree = []
connected_records = {key: key for key in graph.keys()}
for edge_pair, _ in sorted_edge:
if find_parent(connected_records, edge_pair[0]) !=
find_parent(connected_records, edge_pair[1]):
tree.append(edge_pair)
naive_union(connected_records, edge_pair)
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 = kruskal(graph_dict, "D")
print(path) # [('A', 'D'), ('D', 'F'), ('A', 'B'), ('B', 'E'), ('C', 'E'), ('E', 'G')]