0%

最小生成树

本文收录内容:Kruskal和Prim两个算法,基于Python实现的最小生成树

最小生成树的背景:$n$个村庄,每个村庄之间只能修一条路,如何使得总路径最短。

  • Kruskal从最短的边开始寻找,避免回路,加入$n-1$条边后就是最小生成树。
  • Prim是从某个定点出发,定点加入点集$T$,选择与定点相邻距离最短的点加入$T$,并从$T$出发继续寻找,以此类推。

如果对本文有疑问或者想找男朋友,可以联系我,点击此处有我联系方式

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
import numpy as np 


class Graph(object):

def __init__(self, maps):
self.maps = maps
self.nodenum = self.get_nodenum()
self.edgenum = self.get_edgenum()

def get_nodenum(self):
return len(self.maps)

def get_edgenum(self):
count = 0
for i in range(self.nodenum):
for j in range(i):
if self.maps[i][j] > 0 and self.maps[i][j] < 9999:
count += 1
return count

def kruskal(self):
res = []
if self.nodenum <= 0 or self.edgenum < self.nodenum-1:
return res
edge_list = []
for i in range(self.nodenum):
for j in range(i, self.nodenum):
if self.maps[i][j] < 9999:
#按[begin, end, weight]形式加入边
edge_list.append([i, j, self.maps[i][j]])
#按照边的权重进行排序
edge_list.sort(key=lambda a:a[2])
# 统计每个点有几个
group = [[i] for i in range(self.nodenum)]

for edge in edge_list:
for i in range(len(group)):
# 边的起点
if edge[0] in group[i]:
m = i
# 边的终点
if edge[1] in group[i]:
n = i
if m != n:
res.append(edge)
group[n] = group[m] + group[n]
# m点已经走过,清空,防止下次遍历
group[m] = []
return res

def prim(self):
res = []
if self.nodenum <= 0 or self.edgenum < self.nodenum-1:
return res
res = []
# 初始第一个点
seleted_node = [0]
# 剩余的点
candidate_node = [i for i in range(1, self.nodenum)]

while len(candidate_node) > 0:
begin, end, minweight = 0, 0, 9999
for i in seleted_node:
for j in candidate_node:
if self.maps[i][j] < minweight:
minweight = self.maps[i][j]
begin = i
end = j
res.append([begin, end, minweight])
# 加入新的点
seleted_node.append(end)
# 删除已添加的点
candidate_node.remove(end)
return res


if __name__ == '__main__':
maps = [
[0, 7, 100, 3, 100, 5],
[7, 0, 9, 100, 3, 100],
[100, 9, 0, 6, 100, 4],
[3, 100, 6, 0, 8, 10],
[100, 3, 100, 8, 0, 4],
[5, 100 ,4, 10, 4, 0]
]

graph = Graph(maps)
print('邻接矩阵为\n%s'%np.array(graph.maps))
print('节点数据为%d,边数为%d\n'%(graph.nodenum, graph.edgenum))
print('---------------------Kruskal---------------------')
print(graph.kruskal())
print('---------------------Prim------------------------')
print(graph.prim())

感谢上学期间打赏我的朋友们。赛博乞讨:我,秦始皇,打钱。

欢迎订阅我的文章