[고급 알고리즘] Graph(MST): Prim Algorithm

1. Prim Algorithm

• MST를 찾는 알고리즘 입니다.
• 인접 행렬과 우선순위 큐를 사용합니다.

 

Greedy

• 최소 비용의 인접 간선을 선택하여 MST를 만듭니다.

 

2. 동작 순서

 

0. 인접행렬 생성

1. 시작 꼭짓점 선택

2. MST에 간선 추가

• 대상: 트리 정점에 부속된 간선들
• 순서: 가중치가 가장 작은 간선 (우선순위 큐 사용)

 

모든 꼭짓점이 MST에 포함될 때까지 반복합니다.

(모든 간선을 조사한 후 MST에 모든 꼭짓점이 없다면, 해당 그래프에는 MST가 존재하지 않습니다.)

 

3.  구현

static class Edge implements Comparable<Edge> {
    final int dest, weight;

    public Edge(int dest, int weight) {
        this.dest = dest;
        this.weight = weight;
    }

    @Override
    public int compareTo(Edge o) {
        return Integer.compare(this.weight, o.weight);
    }
}

public class MyPrim {
    private final int INF = Integer.MAX_VALUE, NON_EXIST = 0;
    private final Scanner sc;
    private final PriorityQueue<Edge> pq;
    private final BitSet mstV;
    private final int[][] adjMatrix;
    private final int[] minDists;
    private final int vCnt;

    public MyPrim() {
        sc = new Scanner(System.in);
        pq = new PriorityQueue<>();
        vCnt = sc.nextInt();

        adjMatrix = new int[vCnt][vCnt];
        for (int i = 0; i < vCnt; i++) {
            for (int j = 0; j < vCnt; j++) adjMatrix[i][j] = sc.nextInt();
        }

        minDists = new int[vCnt];
        Arrays.fill(minDists, INF);

        mstV = new BitSet(vCnt);
    }

    public int prim(int start) {
        pq.clear();
        mstV.clear();

        minDists[start] = NON_EXIST;
        pq.offer(new Edge(start, NON_EXIST));

        int sum = 0, cnt = 0;

        while (!pq.isEmpty()) {
            Edge curE = pq.poll();
            int dest = curE.dest, weight = curE.weight;

            if (mstV.get(dest)) continue;
            mstV.set(dest);

            sum += weight;
            if (++cnt == vCnt) break;

            for (int neigh = 0; neigh < vCnt; neigh++) {
                if (adjMatrix[dest][neigh] == 0) continue;
                if (adjMatrix[dest][neigh] >= minDists[neigh]) continue;

                minDists[neigh] = adjMatrix[dest][neigh];
                pq.offer(new Edge(neigh, minDists[neigh]));
            }
        }

        return sum;
    }
}

Time Complexity: $O(E\log V)$

인접 행렬 생성: $V^2$

트리 정점 추가: $O(E\log V)$

• 트리 정점에 부속 + 비트리 정점과 인접
• 가중치가 가장 작은 간선

 

출처

• Wiki - Prim Algorithm