최소 신장 트리 (MST) - 크루스칼, 프림

 

📍 정의 및 특징

모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리

 

- 사이클 X

- 에지 중심!

- 노드가 N개일 때, MST를 구성하는 에지 개수는 항상 N-1개

- 대표 : 크루스칼(그리디), 프림 알고리즘

 

#사이클X    #에지   #가중치합   #크루스칼 #프림

 

 

📍 필요 변수

1. 에지 클래스

     - 노드 변수 2개

     - 가중치 변수

2. 그래프 에지 리스트

    - PriorityQueue<Edge> edges

3. 유니온 파인드 배열
    - int[] parent
    - 사이클 판단

4. 에지 개수

    - int useEdge

5. 최소 가중치 합 결과

    - int result

 

 

📍 실행 과정

1. 그래프 에지 리스트, 유니온 파인드 배열 초기화
2. 그래프 데이터를 가중치 기준으로 정렬 (참고)
   
   
3. 가중치가 낮은 에지부터 연결 시도
    : 가중치가 낮은 두 노드의 대표 노드가 다를 경우만 연결 (= 유니온 파인드)
      (∵ 대표 노드가 같으면 사이클 생성되므로)
   
   

   // MST 수행
   int useEdge = 0;
   int result = 0; 
               
   while(useEdge < V - 1) {
       Edge now = pq.poll();
       
       if(find(now.s) != find(now.e)) {
         union(now.s, now.e);
         result += now.v;
         useEdge++;
     }
   }

4. 연결한 에지 개수가 N-1 될 때까지 과정 3 반복
5. 에지 개수 == N -1 일 때, 종료 & 총 에지 비용 출력

 

 

➕ 예제

[백준/JAVA] 1197번: 최소 스패닝 트리

[백준/JAVA] 1414번: 불우이웃돕기

[백준/JAVA] 17472번: 다리 만들기 2

 

---

(참고)

[알고리즘/ 그래프] 최소 스패닝 트리 - 크루스칼(Kruskal)과 프림(Prim) 알고리즘 (Java)

- Do it 알고리즘 코딩 테스트 자바편