8.4.3 크루스칼 알고리즘 테스트 코드 구현

이제 구체적으로 구현합시다. 콘솔 응용 프로젝트를 생성하고 프림 알고리즘에서 사용한 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