#include <stdio.h>

#define TRUE 1 // 방문한 정점에 TRUE값을 준다

#define FALSE 0 // 방문하지 않은 정점에 FALSE값을 준다


#define VERTICES 7 // 최대 정점 수

#define INF 1000L // 정점이 다른정점과 연결되어 있지 않을 때 무한대값으로 표시


// 임의의 그래프를 입력

int adj_mat[VERTICES][VERTICES] = {

{0, 29, INF, INF, INF, 10, INF},

{29, 0, 16, INF, INF, INF, 15},

{INF, 16, 0, 12, INF, INF, INF},

{INF, INF, 12, 0, 22, INF, 18},

{INF, INF, INF, 22, 0, 27, 25},

{10, INF, INF, INF, 27, 0, INF},

{INF, 15, INF, 18, 25, INF, 0} };


int selected[VERTICES]; // 방문표시를 저장하기 위한 배열

int dist[VERTICES]; // 최소값을 저장하기 위한 배열

int get_min_vertex(int n); // n: 정점을 나타내는 변수

void prim(int s, int n); // s: 초기 dist[s]값 초기화, n:정점을 나타내는 변수


void main() {

prim(0, VERTICES);

}


void prim(int s, int n) {

// prim 함수

int i, u, v, min=0;

// i: 정점의 번호를 나타내는 변수, u: 방문한 정점을 나타냄

// v: 방문할 정점을 나타냄, min: 최소거리들의 합을 나타냄


for (u=0; u<n; u++) dist[u]=INF; // 최소값 저장(dist)배열 초기화

dist[s]=0; // 위와 같음

for (i=0; i<n; i++) {

u=get_min_vertex(n); // 최소 정점 불러옴

selected[u]=TRUE; // 불러온 정점 선택함

if (dist[u] == INF)

return;

// 더이상 방문할 정점이 없을 시에 함수 종료

min+=dist[u]; // 최소 거리 합 더함

printf("\n\t%d번째 %c방문 거리=%d, 최소 비용=%d\n", i, u+65, dist[u], min);

// 방문 정점, 간선 출력

for (v=0; v<n; v++)

if (adj_mat[u][v] != INF)

if (!selected[v] && adj_mat[u][v] <dist[v])

dist[v] = adj_mat[u][v];

}

}


int get_min_vertex(int n) {

// 최소 dist[v]값을 갖는 정점을 반환

int v, i; // v:i의 인접 정점, i: 방문한 정점

for (i=0; i<n; i++) {

if (!selected[i]) {

v=i;

break;

}

}


for (i=0; i<n; i++)

if (!selected[i] && (dist[i] < dist[v]))

v=i;

return (v);

}




이건데 get_min_vertex함수에서 맨 마지막 for문부터 return문까지 중단점 다걸어놓고 돌려봤는데

return에 중단점 걸리긴걸리는데 왠걸계속 if하고 return하고 왔다갔다함...왜이러지?