프림(Prim) 알고리즘

Prim 알고리즘이란??

하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST(최소신장트리)를 만들어가는 방식의 알고리즘이다.

알고리즘의 동작 방식

1) 임의의 정점을 하나 선택해서 시작한다.

2) 선택한 정점을 포함한 트리와 인접하는 정점들 중에 최소 비용의 간선이 존재하는 정점을 선택한다. 단, 이 때 싸이클이 생기지 않아야 한다.

3) 모든 정점이 선택될 때 까지 2번을 반복한다.

코드

🤚 참고사항

• 아래 코드는 동작 순서를 기술하였을 뿐 특정 언어의 문법에 종속되지 않는 수도코드 입니다.

👉시간복잡도 : O(V^2)

int n, graph[n][n], parent[n], weight[n];

int prim() {
    for(int i = 0; i < n; i++) {
        weight[i] = -1; // 각각의 노드가 아직 선택되지 않았다는 의미
    }
    weight[0] = 0;
    for(int k = 1; k < n; k++) {
        int minWeight = Integer.MAX_VALUE;
        int minVertex;
        int minParent;
        for(int i = 0; i < n; i++) {
            if(weight[i] < 0) continue; // 아직 트리에 연결되지 않은 노드이므로 제외
            for(int j = 0; j < n; j++) {
                if(weight[j] >= 0) continue; // 이미 선택된 노드이므로 제외(싸이클이 생기므로) ex) 0,1,2 노드가 있을 때 0-1이 선택된 상태일때 2-0을 이어버리면 싸이클 생김
                if(graph[i][j] < minWeight) {
                    minVertex = j; minParent = i;
                    minWeight = graph[i][j];
                }
            }
        }
        parent[minVertex] = minParent;
        weight[minVertex] = minWeight;
    }
    int sumCost = 0;
    for(int i = 0; i < n; i++) sumCost += weight[i];
    return sumCost;
}

우선순위 큐를 이용하여 성능을 개선한 코드

👉시간복잡도 : O(E * logV)

int n, graph[max_n][max_n];

int prim() {
    priority_queue; // 작은 가중치를 갖는 정점이 우선순위가 높도록 구현
    boolean visited[max_n]; // 싸이클이 생기지 않도록 노드를 두번 선택하지 않아야함
    visited[0] = true;
    for(int next = 0; next < n; next++){
        pq.push(<graph[0][next],next>); // <가중치, 노드번호>
    }
	
    int sumCost = 0;
    while(!pq.empty()) {
    	int curr = pq.top().second; // top : 값만 읽어오고 pop은 안함
        int weight = pq.top().first;
        pq.pop();
        if(visited[curr]) continue;
        visited[curr] = true;
        sumCost += weight;
		
        // 새로 추가한 정점과 연결된 간선을 우선순위 큐에 push
        for(int next = 0; next < n; next++)
        	pq.push(<graph[curr][next], next>);
    }
}