[D-11] 최소 신장 트리

📍 최소 신장 트리

✅ 정의

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

✅ 특징

사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않는다.(내부에 유니온 파인드 알고리즘 구현 필수)
N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 항상 N-1개다.

✅ 핵심 이론

1. 에지 리스트로 그래프를 구현하고 유니온 파인드 배열 초기화하기
2. 그래프 데이터를 가중치 기준으로 정렬하기
3. 가중치가 낮은 에지부터 연결 시도하기
4. 과정 3 반복하기
5. 총 에지 비용 출력하기

1. 에지 리스트로 그래프를 구현하고 유니온 파인드 배열 초기화하기

• 에지 중심으로 저장하는 최소 신장 트리는 에지 리스트의 형태로 저장한다.
  edge class는 일반적으로 노드 변수 2개와 가중치 변수로 구성된다.

• 사이클 처리를 위해 유니온 파인드 배열도 함께 초기화된다.
  배열의 인덱스를 해당 자리의 값으로 초기화하면 된다.
  

2. 그래프 데이터를 가중치 기준으로 정렬하기

• 에지 리스트에 담긴 그래프 데이터를 가중치 기준으로 오름차순 정렬한다.
• 에지 리스트의 1개의 객체를 Class로 표현하면 Comparable() 함수를 사용해 높은 자유도로 정렬을 수행할 수 있다.
  

3. 가중치가 낮은 에지부터 연결 시도하기

• 가중치가 낮은 에지부터 순서대로 선택해 연결을 시도한다.
• 그래프에 사이클 형성 유무를 find 연산을 이용해 확인한 후 두 노드를 연결한다.
• 연결은 사이클이 형성되지 않을 때만 union 연산을 이용해 연결한다.
  

4. 과정 3 반복하기

• 전체 노드의 개수가 N개이면 연결한 에지의 개수가 N-1이 될 때까지 과정 3을 반복한다.
  

5. 총 에지 비용 출력하기

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