자료구조 - MST 학습 - Prim algorithm
Prim algorithm
- 정점 하나를 가진 트리에서 시작
- TV = {v1}
- TV : 트리의 정점
- TV = {v1}
- 트리 내의 정점 u와 트리 밖의 정점 v를 잇는 Edge 중 최소 비용을 가진 (u,v)를 트리 Edge로 만든다.
- TE = TV U {u,v}
- 트리 밖의 정점 v도 트리의 정점으로 만든다.
- TV = TV U {v}
- TV = V(G)와 같아지면 종료
Prim algorithm 구현
- 경로 : mst > prim.py
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
95
96import math
# Graph representation : adjacency list
class GNode:
def __init__(self, vertex, weight):
self.vertex = vertex
self.weight = weight
self.link = None
class Edge:
def __init__(self, u, v, w):
self.u = u
self.v = v
self.w = w
class Graph:
def __init__(self, vnum):
self.adjacency_list = [None for _ in range(vnum)]
self.edge_list = []
self.vertex_num = vnum
def __add__node(self, v, unode):
cur = self.adjacency_list[v]
if not cur:
self.adjacency_list[v] = unode
return
while cur.link:
cur = cur.link
cur.link = unode
def insert_edge(self, u, v, w):
unode = GNode(u, w)
vnode = GNode(v, w)
self.__add__node(u, vnode)
self.__add__node(v, unode)
self.edge_list.append(Edge(u, v, w))
def get_min_v(self, w):
_min = math.inf
# 가장 작은 vertex
min_v = None
for weight in w:
for i in range(len(w)):
if _min > w[i]:
_min = w[i]
min_v = i
return min_v
def MST_prim(self):
mst = Graph(self.vertex_num)
TV = set()
w = [math.inf for _ in range(self.vertex_num)]
_from = [None for _ in range(self.vertex_num)]
w[0] = 0
while len(TV) < self.vertex_num:
v = self.get_min_v(w)
TV.add(v)
if _from[v] != None:
mst.insert_edge(v, _from[v], w[v])
w[v] = math.inf
u = self.adjacency_list[v]
while u:
if u.vertex not in TV and u.weight < w[u.vertex]:
w[u.vertex] = u.weight
_from[u.vertex] = v
u = u.link
return mst
def print_edges(self):
for edge in self.edge_list:
print(f'({edge.u}, {edge.v}) : {edge.w}')
if __name__=="__main__":
g = Graph(6)
g.insert_edge(0, 1, 10)
g.insert_edge(0, 2, 2)
g.insert_edge(0, 3, 8)
g.insert_edge(1, 2, 5)
g.insert_edge(1, 4, 12)
g.insert_edge(2, 3, 7)
g.insert_edge(2, 4, 17)
g.insert_edge(3, 4, 4)
g.insert_edge(3, 5, 14)
mst = g.MST_prim()
mst.print_edges()
Posted