MST알고리즘 - 프림(Prim)

구현 과정 이해하기

---

프림 알고리즘은 정점 선택 기반 알고리즘 입니다.

MST(최소 신장 트리)를 찾는 과정은 아래와 같습니다.

1. 시작 정점 아무거나 하나 고르고 시작합니다.

2. 해당 정점에 연결된 모든 간선 중 가중치가 가장 적은 간선을 선택해 정점을 연결합니다.

3. 시작 정점에서부터 연결된 정점까지의 모든 정점에 연결된 간선 중 가중치가 가장 작은 간선을 선택해 연결합니다.

4. 모든 정점이 연결될 때까지 2~3번 과정을 반복합니다.

 

아래와 같은 연결 그래프에서 최소 신장 트리를 찾아내는 구현 과정을 그림으로 확인하면서 이해해보겠습니다.

그림 1: 

1. 시작 정점 아무거나 하나 고르고 시작합니다.

 

그림 2: 

2. 해당 정점과 연결된 모든 간선(초록색으로 표기한 간선) 중 가중치가 가장 작은 간선(빨간색으로 표시)을 선택해
정점(4)을 연결합니다.

 

그림 3:

3. 시작 정점과 연결된 정점까지의 모든 정점(1, 4)에 연결된 간선(초록색으로 표시) 중 가중치가 가장 작은 간선(빨간색으로 표시)을 선택해 정점(3)을 연결합니다.

 

그림 4와 그림 5도 모든 정점이 연결될 때까지 위와 같은 과정을 반복합니다.

그림 6은 모든 정점이 연결된 최소 신장 트리입니다.

"정점의 수 = 간선의 수+1" 식도 성립하고 사이클 없고 가중치 합이 최소인 속성 모두 만족합니다.

 

---

 

구현 과정을 위와 같이 이해해보았다면 이제 java를 이용해 코드로 직접 구현해보겠습니다.

 

Prim Algorithm with Java

---

 

ArrayList<Edge> list = new ArrayList[] 설명

구현과정 그림 설명

queue가 비었다는 것은 모든 정점을 방문했다는 것을 의미한다.

 

5 //노드수
7 //간선수
1 2 7 //정점1 정점2 정점1과2사이의가중치 -->이것이 간선수만큼 반복되어 입력이 들어갑니다.
...

입력이 위와 같이 들어올 때, Prim을 자바로 구현한 코드는 아래와 같습니다.

public class Prim {
    public static class Edge implements Comparable<Edge>{
        int start, end, cost;

        public Edge(int start, int end, int cost){
            this.start = start;
            this.end = end;
            this.cost = cost;
        }

        @Override
        public int compareTo(Edge o) {
            return this.cost - o.cost;
        }
    }

    static ArrayList<Edge>[] list;//각 노드의 연결상태를 저장
    static boolean[] visit;//방문체크용 배열
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int node = Integer.parseInt(br.readLine());
        int edge = Integer.parseInt(br.readLine());

        list = new ArrayList[node+1];
        visit = new boolean[node+1];

        for(int i=1;i<=node;i++){//list 배열 초기화
            list[i] = new ArrayList<>();
        }

        String[] inputStr;
        for(int i=0;i<edge;i++){
            inputStr = br.readLine().split(" ");
            int start = Integer.parseInt(inputStr[0]);
            int end = Integer.parseInt(inputStr[1]);
            int cost = Integer.parseInt(inputStr[2]);
            list[start].add(new Edge(start, end, cost));
            list[end].add(new Edge(start,end,cost));
        }

        br.close();
        System.out.println(MST());

    }

    public static int MST() {
        PriorityQueue<Edge> priorityQueue = new PriorityQueue<>();//우선순위큐는 Edge의 cost에 대한 최소힙으로 구현된다.
        Queue<Integer> queue = new LinkedList<>();//정점 모두 방문하는데 사용할 큐
        int answer = 0;

        queue.add(1);//1노드를 시작정점으로 잡음
        while(!queue.isEmpty()){
            //시작 정점 및 연결된 정점 방문처리
            int curNode = queue.poll();
            visit[curNode] = true;

            for(Edge edge : list[curNode]){
                if(!visit[edge.end])
                    priorityQueue.add(edge);
            }

            //만약 이미 방문한 것 중 가장 작은 가중치가 나올 경우 한번 더 빼서 또 확인
            while(!priorityQueue.isEmpty()){
                Edge edge = priorityQueue.poll();
                if(!visit[edge.end]){
                    queue.add(edge.end);
                    visit[edge.end] = true;
                    answer += edge.cost;
                    break;
                }
            }
        }
        return answer;
    }
}

 

 

reference

---

https://bepoz-study-diary.tistory.com/163

Java 프림 알고리즘(Prim Algorithm)과 크루스칼 알고리즘(Kruskal Algorithm)에 대해

https://blog.naver.com/ssarang8649/220992988177

최소 비용 신장 트리, Minimum Spanning Tree(MST) 프림 알고리즘 JAVA로 구현하기