C로 만드는 자료구조 - Kruskal 알고리즘

Kruskal 알고리즘 

 Kruskal('크루스칼') 알고리즘은 최소 비용 신장 트리를 만드는 방법 중 하나이다. Kruskal 알고리즘은 그래프의 모든 간선을 비용 순으로 정렬한 다음, 낮은 비용을 가지는 간선을 차례대로 선택하여 신장 트리를 완성해 가는 방법이다.

아래 표를 통해 자세히 알아보자

초기화	(1)   그래프 G의 최 소 비용 신장 트리 H를 다음과 같이 초기화한다. H= (V(G),E(H)) 단, (E(H))= 0 (공집합) (2)   그래프 G의 모든 간선을 가중치 값에 따라 오름차순으로 정렬한다.
루프	Step-1	정렬된 간선들 중에서 (1) 가장 가중치가 작으면서 (2) 순환을 발생시키지 않는 간선 e를 추출
	Step-2	그래프 G의 모든 노드가 연결될 때까지 step-1 을 반복한다.

 가장 먼저 신장트리 H를 그래프 G의 모든 노드들을 추가한다. 여기서 간선을 하나씩 추가하는데 kruskal 알고리즘에서 간선을 추가하는데 2가지 조건이 있다.

(1)   정렬된 간선들 중에서 가장 가중치가 작은 간선을 추가한다.

(2)   순환을 발생시키지 않는 간선만 추가한다.

 위 작업을 수행하기 위해서 먼저 그래프 G의 모든 간선들을 가중치를 기준으로 오름차순으로 정렬을 해둔다(초기화 과정에서) 이 과정을 그래프 G의 모든 노드가 연결될 때 까지 지속한다.

아래는 그림으로 Kruskal 알고리즘의 진행과정을 나타내었다.

 초기화 과정은 크게 2가지로 나뉜다. 먼저 그래프 G의 모든 노드를 H에 추가한다. 그리고 그래프 G의 모든 간선을 가중치를 기준으로 오름차순으로 정렬한다.

Step-1 : 정렬된 간선들중에서 가중치가 작은 (2,3)을 추출한다. (2,3)은 신장 트리 H에서 순환 구조를 만들지 않으므로 H에 추가해도 된다.

Step-2: 신장 트리에서 연결되지 않은 노드가 존재하므로 다시 Step-1을 수행한다.

Step-1 : 남은 간선들중에서 가중치가 작은 (3,4)을 추출한다. (3,4)은 신장 트리 H에서 순환 구조를 만들지 않으므로 H에 추가해도 된다.

Step-2: 신장 트리에서 연결되지 않은 노드가 존재하므로 다시 Step-1을 수행한다.

Step-1 : 남은 간선들중에서 가중치가 작은 (1,2)을 추출한다. (1,2)은 신장 트리 H에서 순환 구조를 만들지 않으므로 H에 추가해도 된다.

Step-2: 신장 트리에서 연결되지 않은 노드가 존재하므로 다시 Step-1을 수행한다.

Step-1 : 남은 간선들중에서 가중치가 작은 (0,2)을 추출한다. (0,2)은 신장 트리 H에서 순환 구조를 만들지 않으므로 H에 추가해도 된다.

Step-2: 신장 트리에서 연결되지 않은 노드가 존재하므로 다시 Step-1을 수행한다.

Step-1 : 남은 간선들중에서 가중치가 작은 (0,1)을 추출한다. (0,1)은 신장 트리 H에서 순환 구조를 만들기 때문에 H에 추가하면 안된다. 따라서 (0,1)은 버리고 그다음 작은 (3,5)를 추출한다. (3,5)는 신장 트리 H에서 순환구조를 만들지 않기 때문에 추가해도 된다.

Step-2: 신장 트리에서 연결되지 않은 노드가 존재하지 않으므로 신장 트리가 완성되었고 알고리즘을 종료한다.

코드로 구현

Kruskal 알고리즘을 구현하기 위해서 우리는 앞서 다뤘던 여러 자료구조를 사용할 것이다.

사용할 자료구조는 최소 힙, 스택, 그래프 이다. 

 스택은 신장 트리에서 순환이 존재하는지에 대해 점검하는 함수로 사용할 것이고 최소 힙을 이용하여 간선들중 가중치가 작은 간선을 추출할 것이다.

1. grapmst.h

Graph* mstKruskal(Graph* pGraph);

ArrayMinHeap* orderEdges(Graph* pGraph);

int checkCycle(Graph* pGraph, int fromVertexID, int toVertexID);

 mstKruskal()함수는 실질적으로 최소 비용 신장 트리를 반환하는 함수이고 orderEdges(), checkCycle() 함수는 mstKruskal() 함수 내부에서 실행되며 각각 기존 그래프의 간선을 정렬, 순환구조가 있는지 확인하는 기능을 한다.

2. grapmst.cpp

#include<iostream>
using namespace std;
#include "graphlinkedlist.h"
#include "linkedstack.h"
#include "linkedgraph.h"
#include "grapharrayheap.h"
#include "graphmst.h"


Graph *mstKruskal(Graph *pGraph) {
    Graph *pReturn = NULL;
    int i = 0, maxNodeCount = 0, currentNodeCount = 0, edgeCount = 0, isCycle = 0;
    ArrayMinHeap *pMinHeap = NULL;
    HeapNode *pHeapNode = NULL;
    if (pGraph == NULL) return NULL;

    maxNodeCount = pGraph->maxVertexCount;
    currentNodeCount = pGraph->currentVertexCount;
    edgeCount = pGraph->currentEdgeCount;
    pReturn = createGraph(maxNodeCount);
    if (pReturn == NULL) return NULL;
    pMinHeap = orderEdges(pGraph);
    if (pMinHeap == NULL) return NULL;
    for (i = 0; i < edgeCount; i++) {
        pHeapNode = deleteMinHeapAH(pMinHeap);
        if (pHeapNode != NULL) {
            isCycle = checkCycle(pReturn, pHeapNode->fromVertexID,
                                 pHeapNode->toVertexID);
            if (isCycle == FALSE) {
                if (pReturn->pVertex[pHeapNode->fromVertexID] != USED) {
                    addVertex(pReturn, pHeapNode->fromVertexID);
                }
                if (pReturn->pVertex[pHeapNode->toVertexID] != USED) {
                    addVertex(pReturn, pHeapNode->toVertexID);
                }
                addEdgeWithWeight(pReturn, pHeapNode->fromVertexID,
                                    pHeapNode->toVertexID, pHeapNode->key);
                printf("[%d], : (%d,%d)->%d\n",
                       i, pHeapNode->fromVertexID, pHeapNode->toVertexID,
                       pHeapNode->key);
            }
            free(pHeapNode);

            if (pReturn->currentVertexCount == currentNodeCount) {
                break;
            }
        }
    }
    return pReturn;
}

ArrayMinHeap *orderEdges(Graph *pGraph) {
    int i = 0;
    int edgeCount = 0;
    ArrayMinHeap *pReturn = NULL;
    ListNode *pListNode = NULL;
    List *pEdgeList = NULL;
    if (pGraph == NULL) return NULL;
    edgeCount = pGraph->currentEdgeCount;
    pReturn = createArrayMinHeap(edgeCount);
    for (i = 0; i < pGraph->maxVertexCount; i++) {
        if (checkVertexValid(pGraph, i) == TRUE) {
            pEdgeList = pGraph->ppEdge[i];
            pListNode = pEdgeList->headerNode.pLink;
            while (pListNode != NULL) {
                int vertexID = pListNode->data.vertexID;
                int weight = pListNode->data.weight;
                if (pGraph->graphType == GRAPH_DIRECTED || (pGraph->graphType == GRAPH_UNDIRECTED && i < vertexID)) {
                    HeapNode heapNode = {0,};
                    heapNode.fromVertexID = i;
                    heapNode.toVertexID = vertexID;
                    heapNode.key = weight;
                    insertMinHeapAH(pReturn, heapNode);
                }
                pListNode = pListNode->pLink;
            }
        }
    }
    return pReturn;
}

int pushLSForDFS(Stack* pStack, int nodeID)
{
    StackNode node = {0,};
    node.data = nodeID;
    return push(pStack, node);
}

int checkCycle(Graph *pGraph, int fromVertexID, int toVertexID) {
    int pReturn = FALSE;

    int i = 0;
    int vertextID = 0;
    Stack* pStack = NULL;
    StackNode* pStackNode = NULL;
    ListNode *pListNode = NULL;
    int *pVisited = NULL;

    if (pGraph == NULL) {
        return pReturn;
    }

    pStack = createStack();
    if (pStack == NULL) {
        return pReturn;
    }

    pVisited = (int*) malloc(sizeof(int) * pGraph->maxVertexCount);
    if (pVisited == NULL) {
        printf("Error, malloc() in traversalDFS()\n");
        deleteStack(pStack);
        return pReturn;
    }

    for(i = 0; i < pGraph->maxVertexCount; i++) {
        pVisited[i] = FALSE;
    }

    pVisited[fromVertexID] = TRUE;
    pushLSForDFS(pStack, fromVertexID);

    while(isStackEmpty(pStack) == FALSE) {
        pStackNode = pop(pStack);
        if (pStackNode != NULL) {
            vertextID = pStackNode->data;
            if (vertextID == toVertexID) {
                printf("(%d,%d)-������ ���ΰ� �����մϴ�.\n",
                       fromVertexID, toVertexID);
                pReturn = TRUE;
                break;
            }

            pListNode = pGraph->ppEdge[vertextID]->headerNode.pLink;
            while(pListNode != NULL) {
                int vertexID = pListNode->data.vertexID;
                if (pVisited[vertexID] == FALSE) {
                    pVisited[vertexID] = TRUE;
                    pushLSForDFS(pStack, vertexID);
                }

                pListNode = pListNode->pLink;
            }
        }
    }

    free(pVisited);
    deleteStack(pStack);

    return pReturn;
}