-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathmini_height.py
More file actions
49 lines (44 loc) · 2.25 KB
/
mini_height.py
File metadata and controls
49 lines (44 loc) · 2.25 KB
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
# 가장 큰수 inf
# float('inf')
INF = float('inf')
# 최소 신장 트리
# 가중치 그래프에서 모든 정점들을 연결하는 간선들의 가중치의 합이 최소가 되는 트리를 찾는 문제
# 신장 트리
# n 개의 정점과 n-1 개의 간선으로 구성된 트리
# 그래프에 존재하는 신장 트리의 수
# 정점의 개수와 간선의 개수에 비례해서 증가
# 프림
# 하나의 간선을 선택하면서 최소 신장 트리를 만들어감
'''
1. 임의의 정점 하나 선택
2. 선택한 정점들과 인접하는 정점들 중에 최소 비용의 간선이 존재하는 정점 선택
3. 모든 정점이 선택될때까지 두번때 과정 반복
'''
'''
두 종류의 상호 배타 집합들
1. 트리 정점들: 최소 신장 트리를 만들기 위해 선택된 정점들
2. 비트리 정점들: 아직 선택되지 않은 것
'''
def MST_PRIM(G, s, N): # 그래프, 시작 정점
key = [INF] * N # 가중치를 무한대로 초기화
pi = [None] * N # 트리에서 연결될 부모 정점 초기화
visited = [False] * N # 방문 여부 초기화
key[s] = 0 # 시작 정점의 가중치를 0으로 설정
for _ in range(N):
minIndex = -1
min = INF
for i in range(N):
if not visited[i] and key[i] < min:
min = key[i]
minIndex = i
visited[minIndex] = True # 최소 가중치 정점 방문처리
for v, val in G[minIndex]: # 선택 정점의 인접한 정점
if not visited[v] and val < key[v]:
key[v] = val # 가중치 갱신
pi[v] = minIndex # 트리에서 연결된 부모 정점
# 크루스칼
# 사이클이 생기지 않도록 최소 가중치 간선을 하나씩 선택해서 최소 신장 트리를 찾는 알고리즘
# 1. 간선 선택 과정에서 생성되는 트리를 관리하기 위해 "상호 배타집합 사용"
# 트리에 속한 노드들은 자신을 루트로 하는 서브 트리의 높이를 Rank(랭크)라는 이름으로 저장
# 2. 선택한 간선으로 두개의 트리가 한 개의 트리로 합쳐질 때 각 트리에 해당하는 상호배타집합을 Union연산으로 합침
# 랭크 값이 작은 트리를 랭크 값이 큰 트리의 서브 트리로 포함할 경우, 트리에 포함된 노드들의 랭크 값 수정 불필요