8.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);
    }
}