신장 트리(Spanning Tree)

그래프 내의 모든 정점을 포함하는 트리를 말한다.

• 최소 연결 부분 그래프이다.
  → n개의 노드를 가진 그래프 일 때, n-1개의 간선으로 연결되어 있는 트리

신장 트리 특징

• DFS, BFS 에 이용된 간선을 모으면 그게 바로 신장트리가 된다.
• 하나의 그래프의 여러개의 신장 트리 존재
• 모든 정점이 연결되어 있어야 하고 사이클을 포함해서는 안된다.
• n개의 정점을 n-1개의 간선으로 연결해야 한다.

MST(Minimum Spaning Tree)

간선들의 가중치 합이 최소인 신장 트리

MST를 이용해서 통신망 같은 선로 구축에 최소 비용을 계산할 수 있다.

Kruskal MST 알고리즘

가장 가중치가 낮으면서 사이클을 발생시키지 않는 간선을 선택해나가는 알고리즘

• 그리디 알고리즘으로 분류
• n-1개의 간선이 선택될 때까지 반복

Kruskal 알고리즘 과정

1. 그래프의 간선들을 가중치의 오름차순으로 정렬한다.
2. 가중치가 가장 낮은 간선을 선택한다.
3. 선택한 간선이 사이클을 생성하는지 검사한다.
   • find 사용해서 parent 노드가 같은지 확인
4. 사이클을 생성하지 않으면 선택한 간선을 현재의 MST에 추가한다.
   • mst에 추가하고, union 처리해서 같은 그룹으로 묶기
5. n-1개의 간선이 선택될 때까지 2~4번을 반복한다.

구현

• 간선 예시

n = 7
edges = [
	(4, 7, 18),
	(4, 5, 22),
	(5, 7, 25),
	(5, 6, 27),
	(1, 22, 29),
	(1, 6, 10),
	(3, 4, 12),
	(2, 7, 15),
	(2, 3, 16),
]
mst = []
parent = [i for i in range(n + 1)]

# 간선 가중치의 오름차순으로 정렬
edges.sort(key=lambda x: x[2])

def find(x):
    if x == parent[x]:
        return x
    return find(parent[x])

def union(x, y):
    parent[find(y)] = parent[find(x)]

def kruskal():
    for edge in edges:
		# n-1개의 간선을 선택하면 종료
        if len(mst) == n - 1:
            return
		# 같은 그룹인지 확인
        if find(edge[0]) == find(edge[1]):
            continue
		# 같은 그룹에 속하지 않으면 mst에 추가 + union
        union(edge[0], edge[1])
        mst.append(edge)

mst()

시간 복잡도

간선의 갯수가 E, 점정의 갯수가 V 일 때

1. 가선의 가중치를 오름차순 정렬 : $O(ElogE)$
2. $O(logV)$ 인 Union-Find 연산을 간선을 선택할 때마다 반복 : $O(ElogV)$

전체적인 시간복잡도

E가 V보다 큰 일반적인 경우 $O(ElogV)$ 로 근사될 수 있다.

Kruskal vs Prim

간선의 갯수 E,정점의 갯수 V 일 때
kruskal 알고리즘의 시간복잡도 : $O(ElogE)$
Prim 알고리즘의 시간복잡도 : $O(ElogV)$

따라서 간선의 갯수가 많은 밀집그래프의 경우 크루스칼 알고리즘이 유리하고, 간선의 갯수가 적은 희소 그래프의 경우 프림 알고리즘이 유리하다.

references

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