十一.|十一. Minimum Spaning Tree 1 Kruskal's algorithm 十一.MinimumSpaningTree1Kruskal'sal

Minimum Spaning Tree: 在我看来，就是在图G中包含所有点的tree，并且tree中所有边的权加起来最小。
Kruskal's algorithm：用于求出无向连通图中最小生成---Minimum Spaning Tree（当然也可以求最大生成）
或者在图不连通的情况下，求出最小（最大）森林。
过程：

设置每一个点都是一棵树
先将所有cut(边)由小到大进行sort
尝试所有的边
A. 如果两个端点分别位于两颗树，那么连接两颗树，形成一条边。
B. 如果两个点都在一颗树内，产生了一条环，那么就舍弃。

练习：
有二十个地方，每个地方相互连通，每个连通公路造价各不同，求最小工程造价和具体的施工方案。

import randomclass node(): def __init__(self, num): self.value = https://www.it610.com/article/numdef build_map(nums): prices = {} for j in range(0, nums): for i in range(0, nums): if i != j and j < i: weight = 10 * random.random() name = (i, j) prices[name] = weight return pricesdef quick_sort(array_price, connection_list, low, high): if low < high: middle = find_pivot(array_price, connection_list, low, high) quick_sort(array_price, connection_list, middle + 1, high) quick_sort(array_price, connection_list, low, middle - 1)def find_pivot(array_prices, connection_list, low, high): pivot = high leftwall = lowfor i in range(low, high): if array_prices[pivot]> array_prices[i]: array_prices[leftwall], array_prices[i] = array_prices[i], array_prices[leftwall] connection_list[leftwall], connection_list[i] = connection_list[i], connection_list[leftwall] leftwall += 1array_prices[high], array_prices[leftwall] = array_prices[leftwall], array_prices[high] connection_list[high], connection_list[leftwall] = connection_list[leftwall], connection_list[high]return leftwalldef kruskal(prices, nums): nodes = [] total_prices = 0 add_order = [] # create the node for j in range(0, nums): nodes.append(node(j))prices_list = list(prices.values()) connection_list = list(prices.keys())# sort quick_sort(prices_list, connection_list, 0, len(prices_list)-1)for i in range(0, len(prices_list)): node_1 = connection_list[i][0] node_2 = connection_list[i][1]if nodes[node_1].value != nodes[node_2].value: if node_1 > node_2: value = https://www.it610.com/article/nodes[node_1].value nodes[node_1].value = nodes[node_2].value # refresh represent of those nodes for j in range(0, nums): if nodes[j].value == value: nodes[j].value = nodes[node_2].valueelse: value = nodes[node_2].value nodes[node_2].value = nodes[node_1].value # refresh represent of those nodes for j in range(0, nums): if nodes[j].value == value: nodes[j].value = nodes[node_1].valuetotal_prices += prices_list[i] add_order.append(connection_list[i])print(total_prices, add_order) return total_prices, add_orderprices = build_map(20)kruskal(prices, 20)

【十一.|十一. Minimum Spaning Tree 1 Kruskal's algorithm】求MST的方法不光是kruskal，Prim也是可以的。都是贪心思想。
区别：
prim：一个优先队列，每次选择距离当前部分最近的节点加入，直到所有节点都加入。适合稠密图，多用邻接矩阵。
Kruskal：并查集，每次总是选择权重最小的边加入，直到加入n-1条边为止。适合稀疏图，多用领接表。