이제 프림 알고리즘을 구현해 보아요.
프림 알고리즘에서는 최소 비용의 정점을 선택하는 내부 알고리즘이 필요해요.
프림 알고리즘에서 정점을 선택해 나갈 때 현재까지 선택한 정점에서 갈 수 있는 정점 목록에서 최소 비용의 정점을 선택해야겠죠.
이를 위해 다음과 같은 논리가 필요해요.
정점선택알고리즘(mstree:최소신장트리,graph:원본 그래프)
selectedge:= NULL으로 초기화
seek:= graph의 시작 정점 위치
end:= graph의 마지막 정점 위치
반복(seek가 end가 아닐 때)
edge:=seek에 있는 간선
조건(edge가 mstree에 선택한 정점을 하나만 포함하고 있을 때)
조건(selectedge가 있다면)
조건(selectedge의 비중이 edge의 비중보다 크면)
selectedge:= edge
아니면
selectedge:= edge
mstree에 selectedge의 끝 정점을 추가
mstree에 selectedge를 추가
이제 프림알고리즘을 구현해 보아요.
void SelectVertex(Graph *mstree,Graph *origin);
Graph *Prim(Graph *origin)
{
Graph *mstree = 0;
최소신장트리를 만들 빈 그래프를 생성합니다.
mstree = New_Graph();
원본 그래프의 맨 앞의 정점을 최소신장트리에 추가합니다.
Graph_AddVertex(mstree,Graph_GetFront(origin));
최소신장트리에 정점 개수가 원본 그래프의 정점 개수보다 작다면 정점을 선택하는 것을 반복합니다.
while(Graph_GetVtCnt(mstree)<Graph_GetVtCnt(origin))
{
최적의 정점을 선택하여 최소신장트리에 추가하는 함수는 별도로 구현합시다.
SelectVertex(mstree,origin);
}
return mstree;
}
다음은 최적의 정점을 선택하는 함수입니다.
int IsOnlyOneInclude(Edge *edge, Array *selected);
void SelectVertex(Graph *mstree,Graph *origin)
{
최소신장트리에 선택한 정점 배열과 원본 그래프의 간선 집합을 참조합시다.
Array *selected = mstree->vertexs;
Array *ori_edges = origin->edges;
선택한 간선을 참조할 변수를 초기화합니다.
Edge *selectedge=0;
원본 그래프의 간선 집합의 시작 간선 위치와 마지막 간선 위치를 구합니다.
Iterator seek = 0, end = 0;
Edge *edge = 0;
seek = Array_Begin(ori_edges);
end = Array_End(ori_edges);
간선의 위치를 이동하면서 다음을 반복합니다.
for(seek = seek; seek != end; ++seek)
{
현재 위치의 간선을 참조합니다.
edge = (Edge *)(*seek);
만약 선택한 정점이 간선에 하나만 포함하고 있다면 선택 후보 간선입니다.
if(IsOnlyOneInclude(edge,selected))
{
만약 이미 선택한 후보 간선이 있는지 확인합니다.
if(selectedge)
{
있다면 선택한 후보 간선의 비중이 현재 간선의 비중보다 크면 선택한 후보 간선을 바꿉니다.
if(selectedge->weight>edge->weight)
{
selectedge = edge;
}
}
else
{
만약 선택한 후보 간선이 없을 때는 현재 간선을 후보 간선으로 설정합니다.
selectedge = edge;
}
}
}
최소신장트리에 간선의 끝점을 추가합니다. 여기에서 두 끝점을 추가하지만 함수 내부에서는 같은 정점은 추가하지 않도록 구현하였으므로 선택하지 않은 새 정점만 추가하므로 문제가 없습니다.
Graph_AddVertex(mstree,selectedge->ep1);
Graph_AddVertex(mstree,selectedge->ep2);
최소신장트리에 간선을 추가합니다.
Graph_AddEdge(mstree,selectedge->ep1,selectedge->ep2,selectedge->weight); }
다음은 간선의 끝점이 선택한 정점을 하나만 포함하고 있는지 확인하는 함수입니다.
int IsOnlyOneInclude(Edge *edge, Array *selected)
{
Iterator seek = 0, end = 0;
int cnt = 0;
Vertex vt;
정점의 시작 위치와 끝 위치를 구합니다.
seek = Array_Begin(selected);
end = Array_End(selected);
정점의 위치를 끝까지 이동하면서 다음을 반복합니다.
for(seek = seek; seek != end; ++seek)
{
현재 위치의 정점을 구합니다.
vt = (Vertex)(*seek);
만약 간선에 현재 위치의 정점이 있다면 cnt 변수를 1 증가합니다.
if(Edge_Include(edge,vt))
{
cnt++;
}
}
반복문을 탈출하였을 때 cnt값이 1이면 선택한 정점 중에 하나만 포함하고 있는 간선입니다.
return cnt==1; }