최소 신장 트리 (Minimum Spanning Tree)

728x90

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

📌 최소 신장 트리 특징
사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않음
`N개`의 노드가 있으면 MST를 구성하는 간선의 개수는 항상 `N-1개`

핵심 이론

MST는 데이터를 노드가 아닌 간선 중심(≒ 벨만 포드)으로 저장하므로 인접리스트가 아닌 간선 리스트의 형태로 저장

edge class는 일반적으로 노드 변수 2개와 가중치 변수로 구성

사이클 처리를 위한 유니온 파인드 배열도 선언 및 인덱스를 해당 자리의 값으로 초기화

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

가중치가 낮은 간선부터 순서대로 선택해 연결 시도

이때, 바로 연결하지 않고 해당 간선을 연결했을 때 그래프에 사이클 형성 유무를 확인 후 형성되지 않을 때만 연결

전체 노드 개수가 N개면 연결한 간선의 개수가 N-1이 될 때까지 반복함

간선의 개수가 N-1이 되면 알고리즘을 종료하고, 완성된 MST의 총 간선 비용 출력

MST는 다른 그래프 알고리즘과 달리, 간선 리스트의 형태를 이용해 데이터를 저장한다는 특징을 가짐

또한 사이클이 존재하면 안 되는 특징을 갖고 있으므로 사이클 판별 알고리즘인 유니온 파인드 알고리즘을 내부에 구현해야 함.