최소 신장 트리

신장 트리

신장 트리는 그래프에서 모든 정점에 대한 최소한의 연결만을 남긴 그래프이다. 한 곳으로 도달하는 경우가 두 개 이상 존재하는 경우, 즉 사이클이 존재하는 경우에는 최소한의 연결이라 말할 수 없기 때문에, 모든 위치 하나에서 다른 곳으로 이동하는 경우는 단 한 가지로 결정되도록 항상 트리의 형태를 나타낸다. 최소 비용 신장 트리는 이러한 신장 트리들 중 간선의 가중치 합이 가장 작은 트리이다. -출처 나무위키

 

책에 있는 설명이 이해하기 쉽지 않아서 나무위키를 찾아봤다.

 

최소 신장 트리

각 간선이 가지고 있는 가중치의 합이 최소가 되는 신장 트리이다.

 

최소 신장 트리를 만드는 알고리즘은 "최소한의 비용으로 모든 도시를 연결하는 도로를 건설할 방법을 찾아라" 라는 문제가 주어졌을 때 이를 해결할 아주 좋은 도구가 된다.

새로 건설할 호텔의 배관을 최소의 비용으로 구축하는 일에도 응용할 수 있고, 복잡하게 책상이 놓여 있는 사무실에 전화선을 연결할 때도 최소한의 노력으로 작업을 마칠 수 있는 방법을 얻을 수 있다.

 

프림 알고리즘

프림 알고리즘(Prim's Algorithm)은 그래프에서 최소 신장 트리를 만들어내는 알고리즘 중 하나다.

모든 정점이 최소신장트리에 삽입될 때까지, 최소신장트리에 삽입된 정점들이 가진 가장 가중치가 작은 간선의 target을 최소신장트리에 삽입한다.

사이클이 생기면 삽입하지 않는다.

프림 알고리즘의 구현

프림 알고리즘의 구현은 일견 간단해 보이지만 여기엔 고려해야 할 다음과 같은 두 가지 문제가 있다.

첫 번째 문제는 최소 신장트리의 자료구조로 무엇을 사용할 것인가 하는 문제. 

두 번째 문제는 최소 간선을 골라낼 때 드는 시간비용.

첫 번째 문제는 그래프 사용

두 번째 문제는 우선순위 큐로 해결

크루스칼 알고리즘

크루스칼 알고리즘은 프림 알고리즘과 마찬가지로 그래프에서 최소 신장 트리를 만들어내는 알고리즘이다.

간선을 가중치로 정렬한 뒤, 사이클이 생기지 않는 선에서 순서대로 삽입한다.

 

크루스칼 알고리즘의 구현

크루스칼 알고리즘을 구현할 때 이 정점을 삽입하면 사이클이 생기는지 검사는 분리집합으로 한다.

연결된 정점들끼리 분리집합을 만든다.

분리집합은 효율적으로 중복된 정점을 허용하지 않게 할 수 있다.

 

다음은 소스코드

 

#include "MST.h"
 
void Prim(Graph* G, Vertex* StartVertex, Graph* MST)
{
    int i = 0;
 
    PQNode StartNode = { 0, StartVertex };
    PriorityQueue* PQ = PQ_Create(10);
 
    Vertex* CurrentVertex = NULL;
    Edge* CurrentEdge = NULL;
 
    int* Weights = (int*)malloc(sizeof(int) * G->VertexCount);
    Vertex** MSTVertices = (Vertex**)malloc(sizeof(Vertex*) * G->VertexCount);
    Vertex** Fringes = (Vertex**)malloc(sizeof(Vertex*) * G->VertexCount);
    Vertex** Precedences = (Vertex**)malloc(sizeof(Vertex*) * G->VertexCount);
 
    CurrentVertex = G->Vertices;
    while (CurrentVertex != NULL)
    {
        Vertex* NewVertex = CreateVertex(CurrentVertex->Data);
        AddVertex(MST, NewVertex);
 
        Fringes[i] = NULL;
        Precedences[i] = NULL;
        MSTVertices[i] = NewVertex;
        Weights[i] = MAX_WEIGHT;
        CurrentVertex = CurrentVertex->Next;
        i++;
    }
 
    PQ_Enqueue(PQ, StartNode);
 
    Weights[StartVertex->Index] = 0;
 
    while (!PQ_IsEmpty(PQ))
    {
        PQNode Popped;
 
        PQ_Dequeue(PQ, &Popped);
        CurrentVertex = (Vertex*)Popped.Data;
        Fringes[CurrentVertex->Index] = CurrentVertex;
 
        CurrentEdge = CurrentVertex->AdjacencyList;
        while (CurrentEdge != NULL)
        {
            Vertex* TargetVertex = CurrentEdge->Target;
 
            if (Fringes[TargetVertex->Index] == NULL &&
                CurrentEdge->Weight < Weights[TargetVertex->Index])
            {
                PQNode NewNode = { CurrentEdge->Weight, TargetVertex };
                PQ_Enqueue(PQ, NewNode);
 
                Precedences[TargetVertex->Index] = CurrentEdge->From;
                Weights[TargetVertex->Index] = CurrentEdge->Weight;
            }
            CurrentEdge = CurrentEdge->Next;
        }
    }
 
    for (int i = 0; i < G->VertexCount; i++)
    {
        int FromIndex, ToIndex;
 
        if (Precedences[i] == NULL)
        {
            continue;
        }
 
        FromIndex = Precedences[i]->Index;
        ToIndex = i;
 
        AddEdge(MSTVertices[FromIndex],
            CreateEdge(MSTVertices[FromIndex], MSTVertices[ToIndex],
                Weights[i]));
 
        AddEdge(MSTVertices[ToIndex],
            CreateEdge(MSTVertices[ToIndex], MSTVertices[FromIndex],
                Weights[i]));
    }
 
    free(Fringes);
    free(Precedences);
    free(MSTVertices);
    free(Weights);
 
    PQ_Destroy(PQ);
}
 
void Kruskal(Graph* G, Graph* MST)
{
    int i;
    Vertex* CurrentVertex = NULL;
    Vertex** MSTVertices = (Vertex**)malloc(sizeof(Vertex*) * G->VertexCount);
 
    DisjointSet** VertexSet =
        (DisjointSet**)malloc(sizeof(Vertex*) * G->VertexCount);
 
    PriorityQueue* PQ = PQ_Create(10);
 
    i = 0;
    CurrentVertex = G->Vertices;
    while (CurrentVertex != NULL)
    {
        Edge* CurrentEdge;
 
        VertexSet[i] = DS_MakeSet(CurrentVertex);
        MSTVertices[i] = CreateVertex(CurrentVertex->Data);
        AddVertex(MST, MSTVertices[i]);
 
        CurrentEdge = CurrentVertex->AdjacencyList;
        while (CurrentEdge != NULL)
        {
            PQNode NewNode = { CurrentEdge->Weight, CurrentEdge };
            PQ_Enqueue(PQ, NewNode);
 
            CurrentEdge = CurrentEdge->Next;
        }
 
        CurrentVertex = CurrentVertex->Next;
        i++;
    }
 
    while (!PQ_IsEmpty(PQ))
    {
        Edge* CurrentEdge;
        int FromIndex;
        int ToIndex;
        PQNode Popped;
 
        PQ_Dequeue(PQ, &Popped);
        CurrentEdge = (Edge*)Popped.Data;
 
        FromIndex = CurrentEdge->From->Index;
        ToIndex = CurrentEdge->Target->Index;
 
        if (DS_FindSet(VertexSet[FromIndex]) != DS_FindSet(VertexSet[ToIndex]))
        {
            AddEdge(MSTVertices[FromIndex],
                CreateEdge(MSTVertices[FromIndex],
                    MSTVertices[ToIndex],
                    CurrentEdge->Weight));
 
 
            AddEdge(MSTVertices[ToIndex],
                CreateEdge(MSTVertices[ToIndex],
                    MSTVertices[FromIndex],
                    CurrentEdge->Weight));
 
            DS_UnionSet(VertexSet[FromIndex], VertexSet[ToIndex]);
        }
    }
    for (int i = 0; i < G->VertexCount; i++)
    {
        DS_DestroySet(VertexSet[i]);
    }
    free(VertexSet);
    free(MSTVertices);
}