[그래프] 최소 신장 트리

✔ 최소 신장 트리

최소 신장 트리란?

• 그래프에서 모든 노드를 연결할 때 사용된 엣지들의 가중치의 합을 최소로 하는 트리
• 사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않음
• N개의 노드가 있으면 최소 신장 트리를 구성하는 엣지의 개수는 항상 N - 1개
• 크루스칼 알고리즘 또는 프림 알고리즘을 통해 구현됨

최소 신장 트리 과정

1. 엣지를 중심으로 저장하므로 엣지 리스트로 그래프를 표현
   • 노드 변수 2개와 가중치 변수로 구성됨
2. 사이클 처리를 위한 유니온 파인드 배열도 함께 초기화
3. 엣지 리스트의 데이터를 가중치 기준으로 오름차순 정렬
4. 가중치가 낮은 엣지부터 순서대로 선택해 연결을 시도
   • 바로 연결하지 않고 엣지를 연결했을 때 그래프에 사이클 형성 유무를 find 연산을 이용해 확인
   • 두 노드의 대표 노드가 같다면 두 노드를 연결했을 때 사이클이 만들어지게 됨
   • 사이클이 형성되지 않을 때만 union 연산을 이용해 두 노드를 연결
5. 전체 노드의 개수가 N개이면 연결한 엣지의 개수가 N - 1이 될 때까지 반복
6. 완성된 최소 신장 트리의 총 엣지 비용을 출력

 

Do it! 알고리즘 코딩테스트 with JAVA

https://inf.run/w9Tn