자료구조 - MST 학습 - Kruskal algorithm
Kruskal algorithm
- Edge를 가중치가 작은 것에서 큰 것 순으로 정렬
- 트리에 Edge를 하나씩 추가
- 사이클이 생기면 추가하지 않는다.
- 최소 비용 신장 트리가 완성되면 |E| = |v|-1
Kruskal 구현
경로 : mst > disjoint_set
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# Union Find Algorithm
class DisjointSet:
def __init__(self, vnum):
self.parent = [-1 for _ in range(vnum)]
def simple_find(self, i):
# i가 속한 트리의 루트를 반환
while self.parent[i] >= 0:
i = self.parent[i]
return i
def simple_union(self, i, j):
# i, j must be ROOTS
self.parent[i] = j
# 성능 향상
# 노드의 개수대로 root의 음수 값을 변경한다,(노드가 3개라면 -3)
def collapsing_find(self, i):
root = i
while self.parent[root] >= 0:
root = self.parent[root]
trail = i
while trail != root:
lead = self.parent[trail]
self.parent[trail] = root
trail = lead
return root
def weighted_union(self, i, j):
# i, j must be ROOTS
temp = self.parent[i] + self.parent[j]
if self.parent[i] > self.parent[j]:
self.parent[i] = j
self.parent[j] = temp
else:
self.parent[j] = i
self.parent[i] = temp
if __name__ == "__main__":
ds = DisjointSet(5)
ds.parent[2] = -5
ds.parent[4] = 2
ds.parent[0] = 4
ds.parent[1] = 0
ds.parent[3] = 1
print(ds.parent)
print("the root is {}".format(ds.collapsing_find(3)))
print(ds.parent)경로 : mst > kruskal.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
93from disjoint_set import DisjointSet
import 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 MST_kruskal(self):
mst = Graph(self.vertex_num)
ds = DisjointSet(self.vertex_num)
self.edge_list.sort(key=lambda e: e.w)
mst_edge_num = 0
edge_idx = 0
while mst_edge_num < self.vertex_num-1:
edge = self.edge_list[edge_idx]
if ds.collapsing_find(edge.u) != ds.collapsing_find(edge.v):
mst.insert_edge(edge.u, edge.v, edge.w)
ds.weighted_union(ds.collapsing_find(edge.u),
ds.collapsing_find(edge.v))
mst_edge_num += 1
edge_idx += 1
return mst
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 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_kruskal()
mst.print_edges()
Posted