[알고리즘] ch 7. 그래프(4) - 최소 신장 트리( 크루스칼 알고리즘)

7.5.2 크루스칼 알고리즘 

 

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

 

- 그래프 내 모든 간선의 가중치 정보를 사전에 파악하고 이 정보를 토대로 최소 신장 트리를 구축

- 과정

 

 1) 그래프 내의 모든 간선을 가중치의 오름차순으로 정렬하여 목록을 만듬

  

 2) 단계 1에서 만든 간선의 목록을 차례대로 순회하면서 간선을 최소 신장 트리에 추가. 

 단, 이때 추가된 간선으로 인해 최소 신장 트리 내에 사이클이 형성되면 안됨 

 

- 사이클 탐지 방법으로 분리 집합 이용 

- 각 정점별로 각각의 분리 집합을 만들고, 간선으로 연결된 정점들에 대해서는 합집합을 수행 

- 이때 간선으로 연결할 두 정점이 같은 집합에 속해 있다면 이 연결은 사이클을 이루게 됨 

 

 

ex)

 

- 정점 사이에 있는 모든 간선을 가중치 오름차순으로 정렬 

 A-B : 35

 E-F : 82

 E-H: 98

 G-I : 106

 C-D: 117

 F-H : 120

 B-C : 126 

 B-F : 150

 F-G : 154

 C-F : 162

 C-G : 220 

 A-E : 247

 

 

- 각 정점별로 분리 집합을 만듬 

 

- 가장 작은 가중치를 가진 간선부터 작업 시작

- 첫 번째 간선은 가중치 35인 A-B

- 정점 A와 B는 별개의 분리 집합 원소이므로 A와 B를 최소 신장 트리에 추가하고 간선으로 연결 

- 분리 집합 {A}와 {B}에 대해 합집합을 수행하여 하나의 분리 집합으로 만듬 

 

<그래프>

 

<집합>

 

- 두 번째로 작은 가중치를 가진 간선은 E-F(82)

- E-F를 최소 신장 트리에 추가하고 분리 집합 {E}와 {F}를 합하여 분리 집합으로 만듬 

 

<그래프>

 

<집합>

 

- 그 다음 간선은 E-H(98)

- E는 {E,F}에 , H는 {H}에 소속되어 있어 서로 별개의 분리 집합인 상태 

- 간선 E-H를 최소 신장 트리에 추가하고 {E,H}와 {H}에 대해 합집합 수행 

 

<그래프>

 

<집합>

 

- 다음 순서는 G-I(106)

- G와 I 역시 서로 별개의 분리 집합에 속해 있으므로 최소 신장에 추가 가능 

- 간선 G-I를 최소 신장 트리에 입력하고 {G}와 {I}에 대해서는 합집합 연산을 수행해서 {G,I}를 만듬 

 

<그래프>

 

<집합>

 

- 다음 간선 F-H(120)

- 정점 F와 H는 이미 같은 집합에 속해 있음 

- 간선 양끝에 있는 정점이 같은 집합에 속해 있다면 이 간선으로 인해 그래프에 사이클이 형성되어 있다는 뜻 

- 간선 F-H는 E-F-H에 이르는 사이클이 형성되어 있음

- 간선 F-H는 무시하고 다음 순위의 간선을 채택

 

- 다음 순위의 간선은 C-D(117)

- C와 D는 서로 다른 집합에 소속되어 있으므로 최소 신장 트리에 간선을 추가하고 두 정점을 하나의 집합으로 만듬 

 

<그래프>

 

<집합>

 

- 다음은 B-C(126)

- B와 C는 서로 다른 집합에 속해 있으므로 이 간선을 최소 신장 트리에 추가

- B가 속한 {A,B}와 C가 속한 {C,D}에 대해 합집합 수행 

 

<그래프>

 

<집합>

 

- 다음은 가중치 150을 가진 B-F

- B와 F는 서로 다른 집합에 속해 있으므로 간선 B-F는 최소 신장 트리에 들어갈 수 있음

- 간선 B-F를 최소 신장 트리에 추가하고 B가 소속된 {A,B,C,D}와 F가 소속된 {E,F,H}에 대해 합집합 수행

 

<그래프>

 

<집합>

 

- 다음 순위의 간선은 F-G(154)

- F와 G는 서로 다른 집합에 소속되어 있음 

- 간선 F-G를 최소 신장 트리에 추가하고 {A,B,C,D,E,F,H}와 {G,I}를 하나로 만들기 위해 합집합 수행 

- 모든 정점이 하나의 집합 안에 모여서 최소 신장 트리가 됨 

 

<그래프>

 

<집합>

 

 

 

- 크루스칼 알고리즘 프로그램

 

Disjointset.c

#include "DisjoingSet.h"

//합집합 
//분리 집합을 이루는 트리내의 모든 노드는 뿌리 노드가 나타내는 집합안에 있음
//오른쪽에 있는 집합의 뿌리 노드를 왼쪽에 있는 뿌리 노드의 자식 노드로 만들면 됨
void DS_UnionSet(DisjointSet* Set1, DisjointSet* Set2)
{
	Set2 = DS_FindSet(Set2);
	Set2->Parent = Set1;
}

//집합 탐색 연산 
//원소가 속한 집합 찾기
DisjointSet* DS_FindSet(DisjointSet* Set)
{
	while (Set->Parent != NULL)
	{
		Set = Set->Parent;
	}

	return Set;
}

//집합 생성 
DisjointSet* DS_MakeSet(void* NewData)
{
	DisjointSet* NewNode = (DisjointSet*)malloc(sizeof(DisjointSet));
	NewNode->Data = NewData;
	NewNode->Parent = NULL;

	return NewNode;
}

//집합 소멸 
void DS_DestroySet(DisjointSet* Set)
{
	free(Set);
}

 

 

MST.c

//크루스칼 알고리즘
void Kruskal(Graph* G, Graph* MST )
{
    int           i;
    Vertex*       CurrentVertex = NULL;
    Vertex**      MSTVertices   = (Vertex**) malloc( sizeof(Vertex*) * G->VertexCount );
    DisjointSet** VertexSet     = 
                         (DisjointSet**)malloc( sizeof(DisjointSet*) * 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;

        printf("%c - %c : %d\n", 
            CurrentEdge->From->Data, 
            CurrentEdge->Target->Data, 
            CurrentEdge->Weight );

        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 ( i=0; i<G->VertexCount; i++ )
        DS_DestroySet( VertexSet[i] );

    free( VertexSet );
    free( MSTVertices );
}