[C언어 알고리즘] 7.3.2 프림 알고리즘 구현

[C언어 알고리즘] 7.3.2 프림 알고리즘 구현

---

이제 프림 알고리즘을 구현해 보아요.

프림 알고리즘에서는 최소 비용의 정점을 선택하는 내부 알고리즘이 필요해요.

프림 알고리즘에서 정점을 선택해 나갈 때 현재까지 선택한 정점에서 갈 수 있는 정점 목록에서 최소 비용의 정점을 선택해야겠죠.

이를 위해 다음과 같은 논리가 필요해요.

정점선택알고리즘(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;

}

 

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

 

 콘솔 응용 프로젝트를 생성하고 깊이우선탐색 알고리즘에서 사용한 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;

}

[그림 7.1] 원본 그래프

 

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

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

 

 

 [그림 7.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