최소 신장 트리

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

최소 신장 트리의 특징

• 사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않는다.
• N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 항상 N-1개다.

✅ 최소 신장 트리의 핵심 이론

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

• 최소 신장 트리는 데이터를 노드가 아닌 에지 중심으로 저장하므로 인접 리스트가 아닌 에지 리스트의 형태로 저장한다.
• edge class는 일반적으로 노드 변수 2개와 가중치 변수로 구성된다.
• 사이클 처리를 위한 유니온 파인드 배열도 함께 초기화 한다.
• 배열의 인덱스를 해당 자리의 값으로 초기화 하면 된다.

➡️ 2단계: 그래프 데이터를 가중치 기준으로 정렬하기

• 에지 리스트에 담긴 그래프 데이터를 가중치 기준으로 오름차순 정렬한다.
  • 가중치 합의 최솟값을 찾아야 하므로

➡️ 3단계: 가중치가 낮은 에지부터 연결 시도하기

• 가중치가 낮은 에지부터 순서대로 선택해 연결을 시도한다. 이때 바로 연결하지 않고 이 에지를 연결했을 때 그래프에 사이클 형성 유무를 find연산을 이용해 확인한 후 사이클이 형성되지 않을 때만 union연산을 이용해 두 노드를 연결한다.
  • 단계
    • 1단계: 가중치값이 낮은 에지 선택
    • 2단계: 해당 가중치로 연결된 두 노드를 find연산을 통해 사이클이 형성되는지 확인
    • 3단계: 사이클이 형성되지 않으면(두 노드의 대표 노드가 다를 때) union연산 수행