[C언어] 자료구조 - 가중치 그래프 Weighted Graph + Prim - 2

이제 Prim 알고리즘에 대해서 알아볼 시간을 가질건데 

 

짧게 말하자면 하나의 정점부터 시작하는 것은 같지만

 

앞에 배웠던 Kruskal과 다르게 트리에서 확장시켜

나가는 것이다. Kruskal은 그냥 간선을 오름차순으로 고르면서 나갔다면

 

Prim은 선택한 정점들이 기준이 되는것이다.

즉 n-1번 수행하면 n개의 정점과 이어져서 반복이 끝나고 최소비용 신장트리가 완성될 것이다.

 

알고리즘은 이렇게 되고

ㅊ은 오타인데 ㅋㅋㅋ 이미 넣어서 귀찮음

그림으로 표현하자면 

이런식이다.

코드로 알아본다면 조금 추가해야할 부분이 생기는데

현재까지의 정점들 중에서 가장 가까운 정점을 찾는 과정인데

그래야 트리 기준으로 MST를 만들지 그치? 그래서 dist[]라는 배열을 쓸건디

dist[i]는 현재의 MST에서 i번째 정점까지의 지금까지 알려진 가장 가까운 거리를 저장시킨다

처음에는 시작정점만 0이겠지?? 이미 포함되어있으니??

 

코드로 한번 보면서 익히자

 

int selected[MAX_VTXS];

//MST에 포함되어있는 정점들
int dist[MAX_VTXS];

//거리를 저장한다 그랬지?? 사실 가중치를 저장하는 것임

//인접정점들을 연결하는 간선의 가중치

int getMinVertex()
{
int v, minv = 0, mindist = INF; 

// 3가지 인트 자료형 선언
for(v=0; v<vsize; v++)

// 모든 정점에대해 조사

if( !selected[v] && dist[v]< mindist){

 // MST에 포함되어있지 않은데 가중치가 작다면?
mindist = dist[v];  반복되면서 가중치가 작은 것을 찾겠지?
minv = v;   그리고 그 인덱스를 저장하고

}
return minv; // 그것을 반환하지 ㅎㅎ
}

 

Prim은 어떨까

이렇게 된다.. 짧지만 얘는 여기서 끝내겠다.. ㅋㅋㅋㅋ 힘드렁