[알고리즘] 최소 신장 트리 알고리즘(Minimum Spanning Tree Algorithm) - 코딩밥상

최소 신장 트리(Minimum Spanning Tree)란?

각 간선 마다 가중치(Weight)를 갖는다면 표현할 수 있는 요소가 훨씬 다양해집니다. 신장 트리(Spanning Tree)의 'Spanning'의 뜻은 '떨어져 있는 둘 사이를 다리 등으로 연결한다'라는 뜻입니다. 즉, 신장 트리는 그래프의 모든 정점을 연결하는 트리입니다.

최소 신장 트리(Minimum Spanning Tree)란 여러 간선 중 가중치의 합이 최소가 되는 간선만 남긴 신장 트리입니다. 따라서 최소 가중치 신장 트리(Minimum Weight Spanning Tree)라고도 부릅니다.

 

이러한 특징을 가지는 최소 신장 트리를 만드는 알고리즘에는 대표적으로 프림(Prim)과 크루스칼(Kruskal)알고리즘이 있습니다.

먼저 프림 알고리즘 먼저 정리해 보겠습니다.

---

프림 알고리즘(Prim's Algorithm)

프림 알고리즘을 간략히 정리해보면,

1. 그래프와 노드가 없는 빈 최소 신장 트리를 준비합니다.
2. 그래프에서 임의의 정점을 시작 정점으로 선택하여 최소 신장 트리의 뿌리 노드로 삽입합니다.
3. 최소 신장 트리에 삽입된 정점들과 이 정점들의 모든 인접 정점 사이에 있는 간선의 가중치를 조사합니다. 간선 중에 가장 가중치가 작은 것을 골라 이 간선에 연결된 인접 정점을 최소 신장 트리에 삽입합니다. 단, 새로 삽입되는 정점은 최소 신장 트리에 삽입된 기존 노드와 사이클을 형성해서는 안됩니다.
4. 최소 신장 트리가 그래프의 모든 정점을 연결하면 알고리즘을 종료합니다.

이는 삽입과 삭제가 빠르고 최솟값을 찾는 데 비용도 거의 들지 않는 우선순위 큐를 이용하는것이 적절합니다.

 

구현

void Prim(Graph* G, Vertex* StartVertex, Graph* MST){
    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;
    int i=0;
    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(i=0; i<G->VertexCount; i++){
        int FromIdex, ToIndex;
        
        if(Precedences[i] == NULL) continue;
        
        FromIdex = Precedences[i]->Index;
        ToIndex = i;
        
        AddEdge(MSTVertices[FromIdex], CreateEdge(MSTVertices[FromIdex], MSTVertices[ToIndex], Weights[i]));
        AddEdge(MSTVertices[ToIndex], CreateEdge(MSTVertices[ToIndex], MSTVertices[FromIdex], Weights[i]));
    }
    
    free(Fringes);
    free(Precedences);
    free(MSTVertices);
    free(Weights);
    
    PQ_Destroy(PQ);
}

---

크루스칼 알고리즘(Kruskal's Algorithm)

프림 알고리즘이 최소 신장 트리에 연결된 정점들의 주변 정보를 파악하여 최소 신장 트리를 완성해 나가는 반면,

크루스칼 알고리즘은 그래프 내 모든 간선의 가중치 정보를 사전에 파악하고 이 정보를 토내로 최소 신장 트리를 구축합니다.

간략히 정리해 보자면,

1. 그래프 내의 모든 간선을 가중치의 오름차순으로 정렬하여 목록을 만듭니다.
2. 간선의 목록을 차례대로 순회하면서 간선을 최소 신장 트리에 추가합니다. 단, 이때 추가된 간선으로 인해 최소 신장 트리 내에 사이클이 형성되면 안됩니다.

그렇다면 최소 신장 내에 생기는 사이클을 어떻게 효율적으로 감지할 것이냐 하면 분리 집합을 이용하는 것이 해답이 될 수 있습니다.

각 정점별로 각각의 분리 집합을 만들고, 간선으로 연결된 정점들에 대해서는 합집합을 수행합니다. 이 때 간선으로 연결할 두 정점이 같은 집합에 속해 있다면 이 연결은 사이클을 이루게 됩니다.

 

구현

void Kruskal(Graph* G, Graph* MST){
    Vertex* CurrentVertex = NULL;
    Vertex** MSTVertices = (Vertex**) malloc(sizeof(Vertex*) * G->VertexCount);
    DisjointSet** VertexSet = (DisjointSet**)malloc(sizeof(DisjointSet*) * G->VertexCount);
    
    PriorityQueue* PQ = PQ_Create(10);
    
    int 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_Union(VertexSet[FromIndex], VertexSet[ToIndex]);
        }
    }
}