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

Prim 알고리즘

 Prim('프림') 알고리즘은 최소 비용 신장 트리를 만드는 방법 중 하나이다. Prim 알고리즘은 트리를 점점 확장시켜 최소 비용 신장트릴 만드는 방법이다. 

 Krusal 알고리즘은 처음부터 모든 노드를 추가하고 시작했지만 prim 알고리즘의 시작노드는 1개이다. 또한 krusal 알고리즘은 모든 간선중 최소비용을 가지는 간선을 우선으로 고려했다면 prim 알고리즘은 현재 신장트리가 포함중인 노드에 부속된 간선들 중에서 최소 비용을 가지는 간선을 우선으로 고려한다는 차이점이 있다.

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

초기화	그래프 G에서의 임의의 시작 노드 r을 선택하여, 신장 트리 H를 초기화 V(H) = r E(H) = 0 (공집합)
루프	Step-1	V(H)와 부속된 간선들 중에서 (1) 가장 가중치가 작으면서 (2) 순환 구조를 발생시키지 않는 간선을 추출
	Step-2	그래프 G의 모든 노드가 V(H)에 포함될 때까지 step-1 을 반복한다.

(1)   V(H)에 부속된 간선들 중에서 가장 가중치가 작은 간선을 추가한다.

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

위 작업을 수행은 그래프 G의 모든 노드가 V(H)에 포함될 때까지 반복된다.

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

가장 먼저 임의의 시작노드를 선정한다. 필자는 '1' 노드를 시작 노드로 설정하였다.

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

Step-2: 신장 트리의 노드가 기존 그래프 G의 노드 개수보다 작으므로 다시 Step-1을 수행한다.

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

Step-2: 신장 트리의 노드가 기존 그래프 G의 노드 개수보다 작으므로 다시 Step-1을 수행한다.

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

Step-2: 신장 트리의 노드가 기존 그래프 G의 노드 개수보다 작으므로 다시 Step-1을 수행한다.

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

Step-2: 신장 트리의 노드가 기존 그래프 G의 노드 개수보다 작으므로 다시 Step-1을 수행한다.

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

Step-2: 신장 트리의 노드가 기존 그래프 G의 노드 개수보다 같으므로 신장트리가 완성되었고 알고리즘을 종료한다.

코드로 구현

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

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

 스택은 신장 트리에서 순환이 존재하는지에 대해 점검하는 함수로 사용된다.

1. grapmst.h

struct GraphEdge{
	int vertexId;
    int vertexIdto;
    int weight;
}

int checkCycle(LinkedGraph* pGraph, int fromVertexID, int toVertexID);//순환구조 확인
LinkedGraph* mstPrim(LinkedGraph* pGraph,int vertexID); // 실질적인 신장트리 반환 함수

// 부속된 간선중 가중치가 가장 작은 간선 추출
void getMinWeightEdge(LinkedGraph* pGraph,LinkedGraph* pMST,
							int mstVertexID,GraphEdge *pMinWeightEdge)

int checkEdge(LinkedGraph* pGraph, int fromVertexID, int toVertexID);

#define MAX_INT 9999

 mstPrim()함수는 실질적으로 최소 비용 신장 트리를 반환하는 함수이고  getMinWeightEdge()함수는 metPrim() 함수 내에서 실행되며 부속된 간선들 중에서 가장 가중치가 작은 간선을 선택하는 기능을 한다. checkCycle() 함수는 getMinWeightEdge() 함수 내부에서 실행되며 간선을 선택할 때 순환구조를 만드는지 확인하는 기능을 한다.

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;
}