2020数据结构小学期（四）——Prim算法

1 import numpy as np
2
3
4 class MinTree(object):
5 def create_graph(self, graph, vertex: int, data: [], weight: []):
6 for i in range(vertex):
7 graph.data[i] = data[i]
8 for j in range(vertex):
9 graph.weight[i][j] = weight[i][j]
10
11 def show_graph(self, graph):
12 for link in graph.weight:
13 print(link)
14
15 def prim_algorithm(self, graph, v: int):
16 total = 0
17 visited = [0] * graph.vertex
18 visited[v] = 1
19 h1 = -1
20 h2 = -1
21 min_weight = 10000
22 for k in range(1, graph.vertex):
23 for i in range(graph.vertex):
24 for j in range(graph.vertex):
25 if visited[i] == 1 and visited[j] == 0 and graph.weight[i][j] < min_weight:
26 min_weight = graph.weight[i][j]
27 h1 = i
28 h2 = j
29 print(‘边 %s -> %s 权值： %d ‘ % (graph.data[h1], graph.data[h2], min_weight))
30 total += min_weight
31 visited[h2] = 1
32 min_weight = 10000
33 print(‘最小生成树的权值： ‘, total)
34
35
36 class MGraph(object):
37 def __init__(self, vertex):
38 self.vertex = vertex
39 self.data = vertex * [0]
40 self.weight = [[0 for row in range(vertex)] for col in range(vertex)]
41
42
43 if __name__ == ‘__main__‘:
44 """
45 vertex_data = [‘A‘, ‘B‘, ‘C‘, ‘D‘, ‘E‘, ‘F‘, ‘G‘]
46 weights = [[10000, 5, 7, 10000, 10000, 10000, 2],
47 [5, 10000, 10000, 9, 10000, 10000, 3],
48 [7, 10000, 10000, 10000, 8, 10000, 10000],
49 [10000, 9, 10000, 10000, 10000, 4, 10000],
50 [10000, 10000, 8, 10000, 10000, 5, 4],
51 [10000, 10000, 10000, 4, 5, 10000, 6],
52 [2, 3, 10000, 10000, 4, 6, 10000]]
53 """
54
55 vertex_str = input("请输入顶点序列（以空格分隔）：")
56 vertex_list = vertex_str.split(" ")
57 vertex_data = [char for char in vertex_list]
58 weight_str = input("请输入边序列（以空格分隔）：")
59 weight_list = weight_str.split(" ")
60 weight_list = list(map(int, weight_list))
61 weight_list = np.array(weight_list)
62 weights = weight_list.reshape(len(vertex_data), len(vertex_data))
63 g = MGraph(len(vertex_data))
64 tree = MinTree()
65 tree.create_graph(g, len(vertex_data), vertex_data, weights)
66 tree.show_graph(g)
67 tree.prim_algorithm(g, 0)