8.3.5 프림 알고리즘 테스트 코드 구현

이제 구현한 프림 알고리즘을 이용하여 테스트 하기로 해요.

콘솔 응용 프로젝트를 생성하고 깊이우선탐색 알고리즘에서 사용한 Array.c와 Array.h, Graph.c, Graph.h 파일을 프로젝트 폴더에 복사하고 프로젝트에 추가하세요. 그리고 프림 알고리즘을 구현할 Program.c 파일을 추가합시다.

Graph.h 파일에 정점 개수를 구하는 함수와 시작 정점을 구하는 함수 원형을 선언합시다.

int Graph_GetVtCnt(Graph *graph);
Vertex Graph_GetFront(Graph *graph);

그리고 Graph.c 파일에 두 함수를 구현합시다. 그래프의 정점 개수는 정점을 보관하는 배열의 usage 멤버의 값입니다.

int Graph_GetVtCnt(Graph *graph)
{
    return graph->vertexs->usage;
}

그래프의 시작 정점은 정점을 보관하는 배열의 시작 위치에 있는 정점입니다.

Vertex Graph_GetFront(Graph *graph)
{
    Iterator front = Array_Begin(graph->vertexs);
    return (Vertex)front[0];
}

그리고 간선이 특정 정점을 포함하고 있는지 확인하는 함수를 Graph.h 파일에 선언합니다. 이 함수는 이미 깊이우선탐색 알고리즘에서 구현한 함수입니다.

int Edge_Include(Edge *edge,Vertex pt);

이제 준비를 하였으면 Program.c에 진입점 main함수를 구현합시다.

#include "Graph.h"
Graph * InitSimulation();
Graph *Prim(Graph *origin);
int main()
{
    Graph *origin = 0;
    Graph *mstree = 0;

원본 그래프를 생성하고 테스트에 사용하기 위해 정점과 간선을 추가하는 초기화 함수를 별도로 작성하고 여기서는 호출하여 사용합시다.

    origin = InitSimulation();

원본 그래프에서 프림 알고리즘을 적용하여 최소신장트리를 만드는 함수도 별도로 작성하고 여기서는 호출하여 사용합시다.

    mstree = Prim(origin);

정상적으로 만들었는지 확인하기 위해 그래프의 정보를 출력합시다.

    Graph_View(mstree);

시뮬레이션에 사용한 원본 그래프와 최소신장트리를 해제합니다.

    Delete_Graph(origin);
    Delete_Graph(mstree);
    return 0;
}

다음은 시뮬레이션에 사용할 그래프를 생성하여 정점과 간선을 추가하는 초기화 함수입니다.

Graph * InitSimulation()
{

먼저 그래프를 생성합니다.

    Graph *graph = New_Graph();

정점 A부터 H까지 추가합니다.

    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");

[그림 8.1]처럼 그래프에 간선을 추가합니다.

    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
정점 개수:8
A
D
B
H
C
E
F
G
간선 개수:7
(A ,D):3
(B ,D):3
(B ,H):2
(C ,D):3
(D ,E):3
(E ,F):2
(G ,H):3