알고리즘 - 최소 신장 트리 (MST) - PRIM

📒 PRIM 알고리즘

1️⃣ PRIM 알고리즘

• 정점 중심
• 그래프 표현 : 인접 행렬, 인접 리스트

2️⃣ 하나의 정점에 연결된 간선 중 하나씩 선택해 MST 만드는 알고리즘

• 동작 방식
  • 임의 정점 하나 선택해서 시작
  • 선택한 정점과 인접한 정점 중 최소 비용의 간선이 존재하는 정점 선택
  • 모든 정점이 선택될 때까지 반복

3️⃣ 서로소인 2개의 집합(2 disjoint-sets) 정보 유지

• 트리 정점들(tree vertices) - MST를 만들기 위해 선택된 정점들
• 비트리 정점들(non-tree vertices) - 선택되지 않은 정점들

4️⃣ 알고리즘

• 입력 처리

  BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 입력을 위한 BufferedReader 생성
  StringTokenizer st;
  int V = Integer.parseInt(br.readLine()); // 정점의 개수 입력 받기
  int[][] adjMatrix = new int[V][V]; // 인접 행렬로 그래프 표현
  boolean[] visited = new boolean[V]; // 정점 방문 여부 확인 배열
  int[] minEdge = new int[V]; // 각 정점까지의 최소 간선 비용 저장 배열
  
  for (int i = 0; i < V; i++) {
      st = new StringTokenizer(br.readLine(), " "); // 각 정점 간의 가중치 입력 받기
      for (int j = 0; j < V; j++) {
          adjMatrix[i][j] = Integer.parseInt(st.nextToken());
      }
  }

  • BufferedReader와 StringTokenizer를 사용하여 입력을 처리한다.
  • adjMatrix에 그래프의 가중치 정보를 저장한다.

• 초기화 및 입력된 위치 저장

  Arrays.fill(minEdge, Integer.MAX_VALUE); // 최소 간선 비용 배열을 무한대로 초기화
  minEdge[0] = 0; // 시작 정점의 최소 간선 비용을 0으로 설정
  int cost = 0; // MST 총 비용 초기화
  int i = 0; // MST 구성에 사용된 정점 수

  • minEdge 배열을 무한대로 초기화하여 아직 선택되지 않은 정점들을 나타낸다.
  • 시작 정점의 비용을 0으로 설정하여 탐색의 시작점을 지정한다.
  • cost 변수는 MST의 총 비용을 저장하는 데 사용된다.

• Prim 알고리즘을 통한 탐색

  for (i = 0; i < V; i++) { // 모든 정점에 대해 반복
      int min = Integer.MAX_VALUE; // 최소 가중치를 무한대로 초기화
      int minVertex = -1; // 최소 가중치를 갖는 정점 초기화
      for (int j = 0; j < V; j++) { // 방문하지 않은 정점 중 최소 간선 비용을 가진 정점 찾기
          if (visited[j]) continue; // 이미 방문한 정점은 건너뛰기
          if (min > minEdge[j]) { // 현재 최소 간선 비용보다 작은 경우 갱신
              minVertex = j;
              min = minEdge[j];
          }
      }
  
      if (minVertex == -1) break; // 연결할 정점이 없는 경우 종료
      visited[minVertex] = true; // 선택된 정점을 MST에 포함
      cost += min; // MST 비용에 최소 가중치를 더함
  
      for (int j = 0; j < V; j++) { // 인접한 정점들의 간선 비용 업데이트
          if (!visited[j] && adjMatrix[minVertex][j] != 0 && minEdge[j] > adjMatrix[minVertex][j]) {
              minEdge[j] = adjMatrix[minVertex][j];
          }
      }
  }

  • MST에 포함되지 않은 정점 중 최소 가중치를 가진 정점을 선택하여 방문하고, 해당 간선을 MST에 추가한다.
  • 선택된 정점에서 연결된 모든 간선의 가중치를 확인하고, 최소 가중치 배열을 갱신한다.

• 결과 출력

  System.out.println(i == V ? cost : -1); // 모든 정점이 MST에 포함된 경우 총 비용을 출력, 그렇지 않으면 -1 출력

  • 모든 정점이 MST에 포함되어 있는지 확인하고, 포함되어 있으면 MST의 총 비용을 출력하고, 그렇지 않으면 -1을 출력한다.

• 전체 코드

  package MST.Prim;
  
  import java.io.*;
  import java.util.*;
  
  public class MST_PrimTest {
      public static void main(String[] args) throws IOException {
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 입력을 위한 BufferedReader 생성
          StringTokenizer st;
          int V = Integer.parseInt(br.readLine()); // 정점의 개수 입력 받기
          int[][] adjMatrix = new int[V][V]; // 인접 행렬로 그래프 표현
          boolean[] visited = new boolean[V]; // 정점 방문 여부 확인 배열
          int[] minEdge = new int[V]; // 각 정점까지의 최소 간선 비용 저장 배열
  
          for (int i = 0; i < V; i++) {
              st = new StringTokenizer(br.readLine(), " "); // 각 정점 간의 가중치 입력 받기
              for (int j = 0; j < V; j++) {
                  adjMatrix[i][j] = Integer.parseInt(st.nextToken());
              }
          }
  
          Arrays.fill(minEdge, Integer.MAX_VALUE); // 최소 간선 비용 배열을 무한대로 초기화
          minEdge[0] = 0; // 시작 정점의 최소 간선 비용을 0으로 설정
          int cost = 0; // MST 총 비용 초기화
          int i = 0; // MST 구성에 사용된 정점 수
  
          for (i = 0; i < V; i++) { // 모든 정점에 대해 반복
              int min = Integer.MAX_VALUE; // 최소 가중치를 무한대로 초기화
              int minVertex = -1; // 최소 가중치를 갖는 정점 초기화
              for (int j = 0; j < V; j++) { // 방문하지 않은 정점 중 최소 간선 비용을 가진 정점 찾기
                  if (visited[j]) continue; // 이미 방문한 정점은 건너뛰기
                  if (min > minEdge[j]) { // 현재 최소 간선 비용보다 작은 경우 갱신
                      minVertex = j;
                      min = minEdge[j];
                  }
              }
  
              if (minVertex == -1) break; // 연결할 정점이 없는 경우 종료
              visited[minVertex] = true; // 선택된 정점을 MST에 포함
              cost += min; // MST 비용에 최소 가중치를 더함
  
              for (int j = 0; j < V; j++) { // 인접한 정점들의 간선 비용 업데이트
                  if (!visited[j] && adjMatrix[minVertex][j] != 0 && minEdge[j] > adjMatrix[minVertex][j]) {
                      minEdge[j] = adjMatrix[minVertex][j];
                  }
              }
          }
          System.out.println(i == V ? cost : -1); // 모든 정점이 MST에 포함된 경우 총 비용을 출력, 그렇지 않으면 -1 출력
      }
  }