이제 크루스칼 알고리즘을 구현하기로 해요. 이 책에서는 크루스칼 알고리즘을 구현할 때 그래프를 인접행렬로 표현하지 않고 정점과 간선의 집합체로 정의할게요. 인접행렬로 표현한 소스 코드는 인터넷이나 다른 레퍼런스에 많이 나와있으니 이를 참고하세요.
그래프는 프림 알고리즘을 구현하면서 만든 것을 사용하세요.
void SelectVertex(Graph *mstree,Graph *origin);
Array *MakeSortedEdges(Array *edges);
void SelectEdge(Array *graphs,Array *sorted_edges);
Graph *Kruskal(Graph *origin)
{
Array *sorted_edges=0;
Array *graphs=0;
int vt_cnt_mone = 0;
int ed_cnt=0;
생성할 그래프를 보관할 컬렉션을 생성합니다.
graphs = New_Array();
원본 그래프의 간선 컬렉션을 기반으로 정렬 상태의 간선 컬렉션을 생성합니다. 이 부분은 별도의 함수로 작성합시다.
sorted_edges = MakeSortedEdges(origin->edges);
크루스칼 알고리즘은 간선을 정정 개수 -1 개 만큼을 선택합니다.
vt_cnt_mone = Graph_GetVtCnt(origin)-1;
반복해서 간선을 선택합니다. 간선을 선택하는 부분도 별도의 함수로 작성합시다.
while(ed_cnt<vt_cnt_mone)
{
SelectEdge(graphs,sorted_edges);
ed_cnt++;
}
정상적으로 진행하면 그래프를 보관하는 컬렉션에 최소신장트리 하나만 남습니다. 맨 앞의 그래프를 반환합니다.
return (Graph *)(*Array_Begin(graphs)); }
입력 인자로 전달받은 간선 컬렉션의 간선을 기반으로 정렬 상태의 간선 컬렉션을 생성하는 함수를 작성합시다.
void AddEdge(Array *sorted_edge,Edge *edge);
Array *MakeSortedEdges(Array *edges)
{
Array *sorted_edges = New_Array();
Iterator seek = 0, end = 0;
Edge *edge = 0;
원본 컬렉션의 시작 위치와 끝 위치를 구합니다.
seek = Array_Begin(edges);
end = Array_End(edges);
순차적으로 위치를 이동하여 간선을 참조합니다.
for(seek = seek; seek != end; ++seek)
{
edge = (Edge *)(*seek);
컬렉션에 간선의 비중으로 위치를 찾아 추가합니다. 이 부분은 별도의 함수로 작성합시다.
AddEdge(sorted_edges,edge);
}
return sorted_edges;
}
컬렉션에 간선의 비중으로 위치를 찾는 함수를 작성합시다.
void AddEdge(Array *sorted_edges,Edge *edge)
{
Iterator seek = 0, end = 0;
Edge *stored_edge = 0;
컬렉션의 시작 위치와 끝 위치를 구합니다.
seek = Array_Begin(sorted_edges);
end = Array_End(sorted_edges);
순차적으로 이동하며 간선을 참조합니다.
for(seek = seek; seek != end; ++seek)
{
stored_edge = (Edge *)(*seek);
새로운 간선의 비중이 참조한 간선의 비중보다 작다면 위치를 찾은 것이므로 루프를 탈출합니다.
if(edge->weight < stored_edge->weight)
{
break;
}
}
찾은 위치에 간선을 추가합니다.
Array_Insert(sorted_edges,seek,edge); }
이제 간선을 선택하는 함수를 작성합시다.
int GreedyEdge(Edge *edge,Array *graphs);
void SelectEdge(Array *graphs,Array *sorted_edges)
{
Edge *edge = 0;
int i = 0;
간선 컬렉션의 간선을 순차적으로 참조합니다.
for(i=0; i<sorted_edges->usage;i++)
{
edge = (Edge *)Array_GetAt(sorted_edges,i);
참조한 간선이 탐욕 간선이면 이를 추가한 후에 함수를 종료합니다. 탐욕 간선인지 확인하여 추가하는 부분은 별도의 함수로 작성합시다.
if(GreedyEdge(edge,graphs))
{
return;
}
그렇지 않다면 해당 위치의 간선을 제거합니다. 이 때 참조할 간선의 인덱스는 증가하지 말아야 합니다. for 문에서 증가하므로 여기서 미리 감소합시다.
else
{
Array_Erase(sorted_edges,sorted_edges->base+i);
i--;
}
}
}
탐욕스런 간선인지 확인하여 맞다면 그래프에 추가하는 함수를 작성합시다.
void Merge_Graph(Graph *graph1,Graph *graph2);
int GreedyEdge(Edge *edge,Array *graphs)
{
순차적으로 이동하면서 컬렉션에 보관한 그래프를 참조할 변수를 선언합니다.
Graph *graph=0;
새로 생성하거나 두 개의 그래프를 통합할 그래프를 참조할 변수를 선언합니다.
Graph *graph2=0;
간선의 끝 점이 하나 포함한 그래프를 처음 만날 때 그 위치를 기억할 변수를 선언합니다.
Iterator a=0;
Iterator seek = 0, end = 0;
생성한 그래프를 보관하는 컬렉션의 시작 위치와 끝 위치를 구합니다.
seek = Array_Begin(graphs);
end = Array_End(graphs);
순차적으로 이동하면서 컬렉션에 보관한 그래프를 참조합니다.
for(seek = seek; seek != end; ++seek)
{
graph = (Graph *)(*seek);
만약 간선의 첫 번째 끝점이 포함하는지 확인합니다.
if(Graph_ExistVertex(graph,edge->ep1))
{
만약 간선의 나머지 끝점도 포함하면 사이클이 발생하여 탐욕스런 간선이 아닙니다.
if(Graph_ExistVertex(graph,edge->ep2))
{
return 0;
}
만약 간선의 나머지 끝점을 포함하지 않고 처음 발견한 것이라면 이 위치를 기억합니다.
else
{
if(a==0)
{
a=seek;
}
그렇지 않다면 이전에 발견한 그래프와 현재 위치의 그래프는 병합할 것입니다. 여기에서는 현재 위치의 그래프를 그래프 컬렉션에서 제거하고 루프를 탈출한 후에 병합합시다.
else
{
Array_Erase(graphs,seek);
break;
}
}
}
여기에서도 나머지 끝점을 포함하고 있을 때의 처리는 같습니다.
else
{
if(Graph_ExistVertex(graph,edge->ep2))
{
if(a==0)
{
a=seek;
}
else
{
Array_Erase(graphs,seek);
break;
}
}
}
}
만약 a가 0이면 간선의 끝점을 하나라도 포함하는 그래프가 없는 것입니다. 이 때는 새로운 그래프를 생성하여 그래프 컬렉션에 추가합니다.
if(a==0)
{
graph2 = New_Graph();
Array_PushBack(graphs,graph2);
}
그렇지 않고 루프를 중간에 탈출하였다면 두 개의 그래프를 하나로 통합합니다. 이 부분의 별도의 함수로 작성합시다.
else
{
graph2 = (Graph *)(*a);
if(seek!=end)
{
Merge_Graph(graph2,graph);
}
}
크루스칼 알고리즘에서 간선을 추가하는 과정을 보여주기 위해 현재의 간선 정보를 출력합시다.
printf("%s,%s : %d\n",edge->ep1,edge->ep2,edge->weight);
그래프에 간선의 두 끝점과 간선을 추가합니다. 각 함수에서는 이미 있을 때 필터링하도록 만들었습니다.
Graph_AddVertex(graph2,edge->ep1);
Graph_AddVertex(graph2,edge->ep2);
Graph_AddEdge(graph2,edge->ep1,edge->ep2,edge->weight);
return 1;
}
두 개의 그래프를 하나로 통합하는 함수를 작성합시다.
void Merge_Graph(Graph *graph1,Graph *graph2)
{
Iterator seek = 0, end = 0;
Edge *ed=0;
seek = Array_Begin(graph2->vertexs);
end = Array_End(graph2->vertexs);
graph2의 정점 컬렉션의 시작 위치에서 끝 위치까지 이동하며 graph1에 정점을 추가합니다.
for(seek = seek; seek != end; ++seek)
{
Graph_AddVertex(graph1,(Vertex)(*seek));
}
graph2의 간선 컬렉션의 시작 위치에서 끝 위치까지 이동하며 graph1에 간선을 추가합니다.
seek = Array_Begin(graph2->edges);
end = Array_End(graph2->edges);
for(seek = seek; seek != end; ++seek)
{
ed = (Edge *)(*seek);
Graph_AddEdge(graph1,ed->ep1,ed->ep2,ed->weight);
}
}
이제 구체적으로 구현합시다. 콘솔 응용 프로젝트를 생성하고 프림 알고리즘에서 사용한 Array.c와 Array.h, Graph.c, Graph.h 파일을 프로젝트 폴더에 복사하고 프로젝트에 추가하세요. 그리고 프림 알고리즘을 구현할 Program.c 파일을 추가합시다.
#include <stdio.h> #include "Graph.h" Graph * InitSimulation(); Graph *Kruskal(Graph *origin);
진입점 main 함수에서는 시뮬레이션에 사용할 그래프를 생성하고 크루스칼 알고리즘으로 최소신장트리를 생성하고 생성한 최소신장트리를 보여줍시다.
int main()
{
Graph *origin = 0;
Graph *mstree = 0;
origin = InitSimulation();
mstree = Kruskal(origin);
Graph_View(mstree);
Delete_Graph(origin);
Delete_Graph(mstree);
return 0;
}
시뮬레이션에 사용할 그래프를 생성하는 부분은 프림 알고리즘에서 사용한 것과 같습니다.
Graph * InitSimulation()
{
Graph *graph = New_Graph();
Graph_AddVertex(graph,"A");
Graph_AddVertex(graph,"B");
Graph_AddVertex(graph,"C");
Graph_AddVertex(graph,"D");
Graph_AddVertex(graph,"E");
Graph_AddVertex(graph,"F");
Graph_AddVertex(graph,"G");
Graph_AddVertex(graph,"H");
Graph_AddEdge(graph,"A","B",5);
Graph_AddEdge(graph,"A","D",3);
Graph_AddEdge(graph,"A","E",4);
Graph_AddEdge(graph,"B","D",3);
Graph_AddEdge(graph,"B","H",2);
Graph_AddEdge(graph,"C","D",3);
Graph_AddEdge(graph,"C","G",4);
Graph_AddEdge(graph,"D","H",5);
Graph_AddEdge(graph,"D","E",3);
Graph_AddEdge(graph,"D","F",3);
Graph_AddEdge(graph,"E","F",2);
Graph_AddEdge(graph,"F","G",6);
Graph_AddEdge(graph,"G","H",3);
Graph_View(graph);
return graph;
}
▷ 실행 결과
정점 개수:8 A B C D E F G H 간선 개수:13 (A ,B):5 (A ,D):3 (A ,E):4 (B ,D):3 (B ,H):2 (C ,D):3 (C ,G):4 (D ,H):5 (D ,E):3 (D ,F):3 (E ,F):2 (F ,G):6 (G ,H):3 B,H : 2 E,F : 2 A,D : 3 B,D : 3 C,D : 3 D,E : 3 G,H : 3 정점 개수:8 B H A D C E F G 간선 개수:7 (B ,H):2 (A ,D):3 (B ,D):3 (C ,D):3 (E ,F):2 (D ,E):3 (G ,H):3