[자료구조][C언어] Prim's MST algorithm (프림 알고리즘)

 

Prim's algorithm (프림 알고리즘)

 

MST(Minimum Spanning Tree) 최소비용신장트리를 구하기 위한 알고리즘 중 하나

 

- 시작 정점에서부터 출발해 신장 트리 집합을 단계적으로 확장해나감

   * 시작 단계에서는 시작 정점만이 신장 트리 집합에 포함

 

- 신장 트리 집합에 인접한 정점 중에서 최저 간선으로 연결된 정점을 선택하여 신장 트리 집합에 추가

 

- 이 과정을 신장 트리 집합이 n-1개의 간선을 가질 때까지 반복

 

 

프림 알고리즘 C언어 코드

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_VERTICES 4
#define INF 1000L

int weight[MAX_VERTICES][MAX_VERTICES] = { // 신장트리의 표현 
    {0,1,5,6},
    {1,0,7,2},
    {5,7,0,3},
    {6,2,3,0}
};

int selected[MAX_VERTICES]; //선택된 정점의 정보
int dist[MAX_VERTICES]; // 최소 거리 정보
int parent[MAX_VERTICES]; // 부모 노드 정보 (edge 출력용)

int resultadjMatrix[MAX_VERTICES][MAX_VERTICES] = { 0 }; //인접 리스트 출력용 2차원 배열

int totalcost = 0; // 최소 가중치의 합을 저장

//최소 가중치(dist[v]) 를 갖는 정점 반환
int get_min_vertex(int n) {
    int v, i;
    for (i = 0; i < n; i++) {
        if (selected[i] == 0) { 
            v = i;
            break;
        }
    }
    for (i = 0; i < n; i++) { //최소 거리 판별
        if (selected[i] == 0 && (dist[i] < dist[v])) { 
            v = i;
        }
    }
    return v;
}

//프림 알고리즘
void prim(int s, int n) {
    int i, u, v;
    for (u = 0; u < n; u++) { // dist , selected , parent 초기화
        dist[u] = INF;
        selected[u] = 0; 
        parent[u] = -1;
    }
    dist[s] = 0; // 시작정점의 거리 가중치는 0 으로 설정
    for (i = 0; i < n; i++) {
        u = get_min_vertex(n); // 최소거리를 가지는 정점 저장
        selected[u] = 1; 
        if (dist[u] == INF) return; //경로가 없는 경우 오류처리 

        // 결과 출력용 
        if (parent[u] != -1) { 
            printf("(%d,%d) ", parent[u], u); // 정점 - 정점 출력
            // 인접리스트에 거리 저장
            resultadjMatrix[parent[u]][u] = dist[u];
            resultadjMatrix[u][parent[u]] = dist[u]; 

            totalcost += dist[u];//가중치의 합계산
        }

        //최소 거리 갱신 
        for (v = 0; v < n; v++) {

            if (weight[u][v] != INF) { // u와 연결된 정점이고

                //선택되기 전이면서 weight[u][v] edge의 길이가 기존의 dist[v]보다 작으면
                if (selected[v] == 0 && weight[u][v] < dist[v]) {
                    parent[v] = u; // 출력용 parent[v]에 u를 부모로 갱신
                    dist[v] = weight[u][v]; // dist[v] 값 갱신
                }
            }
        }
    }
}

int main(int argc, char* argv[]) {
    prim(0, MAX_VERTICES); // 0번부터 MAX_VERTCES-1번 정점까지 MST를 구하는 prim 실행

    //출력용
    printf("\n");
    printf("total cost = %d\n", totalcost);
    for (int i = 0; i < MAX_VERTICES;i++) {
        for (int j = 0; j < MAX_VERTICES; j++) {
            printf("%d ", resultadjMatrix[i][j]);
        }
        printf("\n");
    }
    return 0;
}

 

 

 

초기 신장 트리는 weight로 설정해준 이차원 배열로 가정

(출력쪽 내용은 따로 그림으로 넣지 않았음)

 

 

실행결과