프림 알고리즘 설명
조회수 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번 라인부터 뭐하는건지 이해가 잘 안가네요... 혹시 알고리즘이 어떻게 동작하는 건지 설명해 주실 수 있나요
-
(•́ ✖ •̀)
알 수 없는 사용자
댓글 입력