최소 스패닝 트리 (MST; Minimum Spanning Tree)

Tree

백준 1197번 최소 스패닝 트리 문제를 풀면서 학습한 최소 스패닝 트리에 대해 기록으로 남겨놓으려 한다. 다익스트라부터 공부하긴 해야하는데...

주의!!!!
참고한 블로그 글을 다시 보기 위함도 있고 나 스스로 이해한 부분을 다시 체크하는 거라 틀린 내용이 있을 수 있다. 

 

https://www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

---

최소 스패닝 트리 (MST; Minimum Spanning Tree)란?

 - 간선이 가장 적은 그래프

- n개의 정점과 (n-1)개의 간선으로 이루어진 트리

- 트리의 특수한 형태로 사이클이 존재하지 않는다.

 

MST 구현 방법

1. 크루스칼 알고리즘

그리디 알고리즘의 일종으로 가중치의 값이 가장 작은 값부터 선택해 모든 정점을 최소 비용으로 연결해 최적의 답을 구하는 알고리즘

 

1. 그래프의 간선을 가중치의 오름차순 정렬
2. 가중치가 가장 적은 값부터 선택하는데 이 때 사이클이 존재하지 않을 경우에만 선택한다.
   - 사이클이 존재하는지 확인하는 방법 나는 유니온 파인드 알고리즘을 사용했다.
3. 선택한 간선을 MST 집합에 추가

 

사이클이 존재하는지 확인하기 

1) 무향 그래프인 경우

① Stack

② Union-Find

여러 노드가 존재할 때, 어떤 노드를 같은 집합으로 묶어주고, 다시 어떤 두 노드가 같은 집합에 있는지 확인하는 알고리즘으로 Union 연산과 Find 연산으로 나누어진다.

Union 연산

# 두 원소가 속한 집합을 합치기
def union(a, b):
    a = find(a)
    b = find(b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

Find 연산

# 특정 원소가 속한 집합을 찾기
def find(x):
    # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
        return find(parent[x])
    return x

 

2) 유향 그래프인 경우

visited 배열, finished 배열

https://sosoeasy.tistory.com/35

그래프에 사이클이 있는지 확인하는방법

 

2. 프림 알고리즘

선택해야하는 간선의 개수가 너무 많을 때 사용하는 알고리즘으로 다익스트라 알고리즘과 유사하다.

1. 임의의 정점을 선택하고,(정렬X)

2. 해당 정점에서 갈 수 있는 간선을 min heap에 넣는다.

3. 최소값을 뽑아 해당 정점을 방문 안했다면 선택한다.

 

 

출처:

https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html

https://sosoeasy.tistory.com/35

https://hillier.tistory.com/54

https://ssungkang.tistory.com/entry/Algorithm-%EC%9C%A0%EB%8B%88%EC%98%A8-%ED%8C%8C%EC%9D%B8%EB%93%9CUnion-Find

그래프에 사이클이 있는지 확인하는방법