프림 알고리즘 설명

조회수 1372회

include

define MAX 7 //노드의 개수

define INF 1000 //간선의 가중치가 없는 경우 무한대 표시

void prim();

int w[MAX][MAX] = { {0, 100, 20, 85, 10, 52, 13}, {100, 0, 40, 5, 58, 5, 45}, {20, 40, 0, 25, 10, 49, 1}, {85, 5, 25, 0, 41, 18, 32}, {10, 58, 10, 41, 0, 65, 1}, {52, 5, 49, 18, 65, 0, 50}, {13, 45, 1, 32, 1, 50, 0} };//가중치 행렬. 각 행은 각 노드에서 인접 노드로 가는 가중치를 나타냄

char alph[MAX] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };

void main() {

prim();
printf("\n");

}

void prim() {

int n, lnum;
int d[MAX];//거리 저장 배열
int v[MAX];//방문 확인 배열
int start[MAX];
int finish[MAX - 1];

int i, j, min, idx, tmp, sum;//i,j,tmp 루프용 인덱스 sum = 거리 총합 
n = MAX;
lnum = n - 1;
sum = 0;

for (i = 0; i < n; i++) {
    d[i] = w[1][i];
    v[i] = -1;
}//거리를 모두 1번째 row로 초기화


d[1] = -1;
idx = 1;
start[0] = 1;

for (i = 0; i < n - 1; i++) {
    min = 999999;
    for (tmp = 0; tmp < n; tmp++) {
        if (d[tmp] != 0 && d[tmp] != -1 && d[tmp] != 1000) {
            if (tmp == 0) min = d[tmp];
            else
                if (min > d[tmp]) {
                    min = d[tmp];
                }
        }
    }

////////////////////////////64번 라인 for (j = 0; j < n; j++) for (tmp = 0; tmp < n; tmp++) if (d[j] == -1 && w[j][tmp] == min) start[i + 1] = j;

    for (j = 0; j < n; j++) {
        if (d[j] != -1 && min >= d[j]) {
            min = d[j];
            finish[i] = j;
            v[idx] = j;
            idx = j;
        }
    }
    sum = sum + min;
    d[idx] = -1;
    v[i] = idx;

    if (i == n - 2) break;
    for (j = 0; j < n; j++) {
        if (d[j] > w[idx][j]) {
            d[j] = w[idx][j];
            if (i + 1 != n - 1) start[i + 1] = idx;
        }
    }

}

printf("result of prim algorism : ");

for (i = 0; i < n - 1; i++) {
    printf("\n(%c, %c ) ", alph[start[i]], alph[finish[i]]);
} printf(" ");
printf("Sum = %d ", sum);

}

출처: https://pekaholic.tistory.com/73 [PekaHolic] 프림 알고리즘을 c언어로 구현할 일이 생겨서 인터넷에서 코드를 찾았는데 주석이 하나도 안달려있어서 64번 라인부터 뭐하는건지 이해가 잘 안가네요... 혹시 알고리즘이 어떻게 동작하는 건지 설명해 주실 수 있나요

  • (•́ ✖ •̀)
    알 수 없는 사용자

답변을 하려면 로그인이 필요합니다.

프로그래머스 커뮤니티는 개발자들을 위한 Q&A 서비스입니다. 로그인해야 답변을 작성하실 수 있습니다.

(ಠ_ಠ)
(ಠ‿ಠ)