• 그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리
• MST
  • 크루스칼 → 간선 위주
  • 프림 → 정점 위주
• 최소 신장 트리의 특징
  • 사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않음
  • N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 항상 N - 1개

핵심 이론

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

• 최소 신장 트리는 데이터를 노드가 아닌 에지 중심으로 저장하므로 인접 리스트가 아닌 에지 리스트의 형태로 저장
• 사이클 처리를 위한 유니온 파인드 리스트 초기화

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

• 에지 리스트에 담긴 그래프 데이터를 가중치 기준으로 오름자순 정렬

• 오름차순 정렬은 input 데이터의 순서 조정을 통해 높은 자유도로 정렬할 수 있음

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

• 바로 연결하지 않고 이 에지를 연결했을 때 그래프에 사이클 형성 유무를 find 연산을 이용해 확인할 후 사이클이 형성되지 않을 때만 union 연산을 이용해 두 노드 연결

4. 과정 3 반복하기