[알고리즘] 최소 신장 트리(minimum spanning tree)

1. 최소 신장 트리란

그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리를 말한다.

 

2. 특징

• 그래프는 사이클을 포함하지 않는다.(사이클이 포함되면 가중치의 합이 최소가 될 수 없기 때문)
• N개의 노드가 있을 경우, 최소 신장 트리를 구성하는 에지의 개수는 N-1개이다.
• 에지 리스트의 형태로 데이터를 담는다.
• 사이클을 확인하는 로직은 유니온 파인드 내부에 구현해야 한다.

 

3. 알고리즘 로직

1) 데이터를 그래프로 구현 및 유니온 파인드 배열 초기화

• 그래프는 인접 리스트가 아닌 에지 리스트로 구현한다.

• 유니온 파인드 배열은 사이클 처리를 위함

2) 그래프를 가중치 기준으로 정렬

• 가중치를 기준으로 오름차순 정렬한다.
• 위의 표를 기준으로 봤을 때 에지는 6, 3, 5, 2, 1, 4인덱스의 노드 순으로 정렬된다.

3) 가중치가 낮은 에지부터 연결 시도

• 가중치가 낮은 에지부터 연결하는데 연결 했을 때, 그래프의 사이클 형성 유무를 find연산으로 확인한다.
• find연산의 결과로 사이클이 형성되지 않을 때만, union연산하여 두 노드를 연결한다.

4) 3) 반복

• 연결한 에지의 개수가 N-1개가 될 때까지 3)을 반복한다.

5) 총 에지 비용 출력

• 에지의 개수가 N-1개가 되면 반복문을 종료하고, 완성된 최소 신장 트리에서 총 비용을 출력한다.

 

4. 최소 신장 트리 문제 풀어보기