Prim Algorithm Coding

Prim을 위해 만들어야할 것

1. priority queue
2. 노드 Marking 배열
3. 그래프

#include <cstdio>
#include <vector>

using namespace std;

//TRI를 만들 것 노드, 노드 , wight 형태로 저장되는 것
class TRI {
public:
    int a, b, w;
};

//priority queue
class PQ {
public:
    int n;
    TRI Arr[1000];
    PQ(); //생성자
    TRI Delete(); //삭제
    void Insert(TRI x); //삽입
    int isEmpty(); //비어있는지 확인
};

PQ::PQ(){
    n = 0;
}

int PQ::isEmpty(){
    return n == 0; //n에 들어있는게 없다면 0을 리턴
}

//priority queue insert
void PQ::Insert(TRI x){
    //현재 n개가 들어있고, n까지 채워져있음 (1부터 n까지 들어있음)
        int i;
    Arr[n] = x;
        Arr[n+1] = x;  // 항상 n+1에 삽입 (1-based 인덱스)
        i = n+1;       // 새로운 값이 들어간 위치는 n+1
        n = n+1;       // n 값 증가
        // 힙의 조건을 만족하도록 상위 노드들과 비교하면서 정렬

    //현재 삽입한 곳과, 내 부모 노드랑 비교했을 때 부모노드보다 내 값이 작으면 바꾸는 과정을 반복
    //priority queue의 특징
    while (i > 1 && Arr[i].w <Arr[i/2].w){
        swap(Arr[i],Arr[i/2]);
        i = i/2;
    }
}

TRI PQ::Delete(){
    TRI ret = Arr[1];
    int i,j;
    if(n == 1) {n = 0; return ret;} // n이 1인 경우를 처리
    Arr[1] = Arr[n]; //n번에 있는 제일 끝 값을 제일 위로 올리고, 제일 작은 값을 return해준다.
    i = 1;
    n = n-1;
    while(1){
        //왼쪽 child가 n보다 큰 경우 >> 왼쪽 자식 노드가 없는 것(+오른쪽)
        if(i*2 > n) break;
        // 오른쪽 child가 n보다 큰 경우 >> 오른쪽 자식 노드가 없는 것
        else if(i * 2 +1 > n){//left child only
            if(Arr[i*2].w < Arr[i].w){ //왼쪽 child와 비교하여 내가 더 크면 바꿈
                swap(Arr[i*2], Arr[i]);
                i = i*2;
            }
        }
        else{ //Left and right child exists
            //자식 노드 둘 다보다 큰 경우
            if(Arr[i].w > Arr[i*2].w || Arr[i].w > Arr[i*2+1].w){
                //왼쪽 노드가 오른쪽 노드보다 작은 경우
                if (Arr[i*2].w < Arr[i*2+1].w) j = i*2;
                //오른쪽 노드가 왼쪽 노드보다 작은 경우
                else j = i*2+1;
                swap(Arr[i], Arr[j]);
                i = j;
            }
            //왼쪽 노드보다 크고, 오른쪽 노드보다 작거나 같은 경우
            else if (Arr[i].w > Arr[i*2].w || Arr[i].w <= Arr[i*2+1].w){
                j = i*2;
                swap(Arr[i], Arr[j]);
                i = j;
            }
            //오른쪽 노드보다 크고, 왼쪽 노드보다 작거나 같은 경우
            else if(Arr[i].w <= Arr[i*2].w && Arr[i].w > Arr[i*2+1].w){
                j = i*2+1;
                swap(Arr[i], Arr[j]);
                i = j;
            }
            //자식 노드 둘 다보다 작은 경우
            else break;
        }
    }
    return ret;
}

PQ Q;
int n, m;
vector<pair<int, int>> Edges[1000]; //순서쌍이므로
int M[1000] = {0};//노드를 마킹하는 배열

int main(){
    int c, i, a,b, w;
    TRI x, y;
    scanf("%d %d", &n, &m);
    for(i =0; i < m; i++){
        scanf("%d %d %d", &a, &b, &w);
        Edges[a].push_back(make_pair(b,w));
        Edges[b].push_back(make_pair(a,w)); //그래프 생성
    }
    c = 1;
    M[c] = 1;
    
    //1번 노드에 대해서 edge를 queue에 집에넣음
    for(i = 0; i <Edges[c].size(); i++){
        x.a = c;
        x.b = Edges[c][i].first;
        x.w = Edges[c][i].second;
        Q.Insert(x);
    }
    
    while(Q.isEmpty() == 0){
        y = Q.Delete();//priority queue에서 w가 제일 작은 것 하나 가져옴(delete)
        // 둘 다 마킹이 되어있는 경우 아무것도 하지 않는다. (사이클)
        if(M[y.a] == 1 && M[y.b] == 1) continue;
        else{
            printf("Edge from Node %d to Node %d of Weight %d Selected. \n", y.a, y.b, y.w);
            c = y.b;
            M[c] = 1;
            //해당 노드에 대해서 edge를 queue에 집에넣음
            for(i = 0; i <Edges[c].size(); i++){
                if(M[Edges[c][i].first] == 0){ // 방문하지 않은 노드로 가는 간선만 큐에 삽입
                    x.a = c;
                    x.b = Edges[c][i].first;
                    x.w = Edges[c][i].second;
                    Q.Insert(x);
                }
            }
        }
    }
    
    return 0;
}

알맞게 prim이 실행된다는 것을 알 수 있음

예시

5 10

1 2 10

2 3 1

1 5 6

1 4 5

2 4 4

2 4 3

4 5 2

3 4 9

3 5 4

5 3 6