[C언어 알고리즘] 7.4.1 크루스칼 알고리즘 구현

[C언어 알고리즘] 7.4.1 크루스칼 알고리즘 구현

---

이제 크루스칼 알고리즘을 구현하기로 해요. 이 책에서는 크루스칼 알고리즘을 구현할 때 그래프를 인접행렬로 표현하지 않고 정점과 간선의 집합체로 정의할게요. 인접행렬로 표현한 소스 코드는 인터넷이나 다른 레퍼런스에 많이 나와있으니 이를 참고하세요.

 

그래프는 프림 알고리즘을 구현하면서 만든 것을 사용하세요.

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