신장 트리

신장 트리란?

 

Spanning Tree, 또는 신장 트리라 불린다. 원래의 그래프의 모든 노드가 연결되어 있으면서 트리의 속성을 만족하는 그래프를 말한다.

 

조건은 다음과 같다

 - 본래의 그래프의 모든 노드를 포함해야한다.

 - 모든 노드가 서로 연결되어야 한다.

 - 트리의 속성을 만족시켜야 한다. (사이클이 존재하지 않는다.)

 

 

 

최소 신장 트리 MST

가능한 ST 중에서 간선의 가중치 합의 최소인 ST를 지칭한다.

 

최소 신장 트리 알고리즘

 그래프에서 최소 신장 트리를 찾을 수 있는 알고리즘이 존재한다.

대표적으로 크루스 칼 알고리즘과 프림 알고리즘이 있다.

 

1) 크루스칼 알고리즘

 1. 모든 정점을 독립적인 집합으로 만든다.

 2. 모든 간선을 비용 기준으로 정렬하고, 비용이 작은 간선부터 양 끝의 두 정점을 비교한다

 3. 두 정점의 최상위 정점을 확인하고 서로다를 경우 두 정점을 연결한다 (사이클 방지)

 

- 즉 탐욕 알고리즘을 기초로 하고 있다.

 

이 크루스 칼 알고리즘에서는 사이클을 돌지 않는 간선을 찾아야 하는데 여기서 사이클의 여부를 체크하는 Union-Find알고리즘을 사용할 수 있다.

 

Disjoint Set을 표현할 때 사용되는 알고리즘으로 트리 구조를 활용하는 알고리즘이다.

간단하게 노드들 중 연결된 노드를 찾거나 노드들을 서로 연결할 때 사용한다.

 

Disjoint Set은 서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조로

공통 원소가 없는 상호 배타적인 부분 집합들로 나눠진 원소들에 대한 자료구조이다.

 

모든 노드들을 개별 집합으로 나눈 뒤 연결하는 간선에 대한 정접이 같은 집합에 속하지 않으면 된다.

각 부분집합의 최상위 노드가 같은 지 확인하면 같은 집합인지 아닌지 확인할 수 있다.

 

Union-Find 알고리즘의 고려할 점

 

Union 순서에 따라서 최악의 경우 링크드 리스트와 같은 형태가 될 수 있으며 이때 시간 복잡도가 O(N)이 될 수 있다.

따라서 해결하기 위해 union-by-rank, path compression기법을 사용한다.

 

 

1) union-by-rank 기법

 

각 트리에 대한 높이를 기억해두고 Union시 높이가 다르면  작은 트리를 큰 트리에 붙임

만약 높이가 같다면 한쪽의 트리의 랭크를 1 증가시키고 트리를 union 한다.

 

union-by-rank 기법을 사용하면  높이가 h인 트리를 만들기 위해선 2n개의 원소가 필수적으로 필요하다 (h-1 트리를 만들기 위한 최소 원소가 n 개라 가정) 이렇게 되면 시간 복잡도를 O(logn)으로 낮출 수 있다.

 

 

2) path compression 기법

 

Find를 실행한 노드에서 거쳐간 노드를 루트에 디렉트로 연결하는 기법이며 Find를 실행한 노드는 이후 루트 노드를 바로 알 수 있다.

크루스 칼 알고리즘에서

1) Union을 할 경우 union-by-rank기법을 이용해 각 트리를 합치고

2) Find를 할 경우 path compression기법을 이용해 사이클을 검사하면

시간 복잡도가 O(Mlog*N)을 가지며 이 값을 거의 상수 O(1)과 같다고 할 수 있다.