프림 알고리즘 C 언어로 구현

프림 알고리즘 Prim algorithm

• 프림 알고리즘
  • 시작 정점을 선택한 후, 정점에 인접한 간선중 최소 간선으로 연결된 정점을 선택하고, 해당 정점에서 다시 최소 간선으로 연결된 정점을 선택하는 방식으로 최소 신장 트리를 확장해가는 방식
• Kruskal's algorithm 과 Prim's algorithm 비교
  • 둘다, 탐욕 알고리즘을 기초로 하고 있음 (당장 눈 앞의 최소 비용을 선택해서, 결과적으로 최적의 솔루션을 찾음)
  • Kruskal's algorithm은 가장 가중치가 작은 간선부터 선택하면서 MST를 구함
  • Prim's algorithm은 특정 정점에서 시작, 해당 정점에 연결된 가장 가중치가 작은 간선을 선택, 간선으로 연결된 정점들에 연결된 간선 중에서 가장 가중치가 작은 간선을 택하는 방식으로 MST를 구함

구현 방법

1. 임의의 정점을 선택, '연결된 노드 집합'에 삽입
2. 선택된 정점에 연결된 간선들을 간선 리스트에 삽입
3. 간선 리스트에서 최소 가중치를 가지는 간선부터 추출해서,
   • 해당 간선에 연결된 인접 정점이 '연결된 노드 집합'에 이미 들어 있다면, 스킵함(cycle 발생을 막기 위함)
   • 해당 간선에 연결된 인접 정점이 '연결된 노드 집합'에 들어 있지 않으면, 해당 간선을 선택하고, 해당 간선 정보를 '최소 신장 트리'에 삽입
4. 추출한 간선은 간선 리스트에서 제거
5. 간선 리스트에 더 이상의 간선이 없을 때까지 3-4번을 반복

void    prim(LinkedGraph *graph)
{
    LinkedGraph    *ret = createLinkedGraph(graph->maxVertexCount);
    // 값을 저장할 그래프
    int    selected[graph->maxVertexCount];
    ListNode    *temp;
    int INF = 999999999;
    int            i = 0;

    for(int i = 0; i < graph->maxVertexCount; i++)
        selected[i] = INF; // 선택되지 않은 값들은 INF로 한다.
    while (i < graph->maxVertexCount)
    {
        temp = graph->ppAdjEdge[i]->headerNode.pLink;
        int min = 999999999;
        int id = temp->data.vertexID;
        while(temp) // 노드 간 최소 값을 구한다.
        {    
            if (selected[i] && min > temp->data.weight)
            {
                min = temp->data.weight;
                id = temp->data.vertexID;
            }
            temp = temp->pLink;
        }
        if (selected[i] && min != INF) 
        // 선택되지 않았고, 최소값이 INF가 아니라면 ret에 저장해준다.
        {
            addVertexLG(ret, id);
            addVertexLG(ret, i);
            addEdgewithWeightLG(ret, i, id, min);
            selected[i] = 0;
        }
        i++;
    }
    displayLinkedGraph(ret); // 결과 출력!
}