12.4.1 크루스칼 알고리즘 구현 [디딤돌 자료구조와 알고리즘 with C++]

12.4.1 크루스칼 알고리즘 구현

간선은 프림 알고리즘에서 구현한 것과 차이가 없습니다. 그래프도 대부분 비슷합니다. 여기에서는 차이가 있는 부분만 설명할게요.

크루스칼 알고리즘.zip

 

이번에는 간선을 선택할 때 간선의 비중이 같을 때 그래프에 먼저 추가한 간선을 선택하게 합시다. 이를 위해 Graph에 간선을 추가하는 부분을 수정할게요.

bool Graph::AddEdge(string vt1, string vt2,int weight)//간선 추가

{

    if(Exist(vt1)&&Exist(vt2))

    {

        if(Exist(vt1,vt2))

        {

            return false;

        }

        CEIter seek = edges.begin();

        CEIter last = edges.end();

        for(  ;seek != last; ++seek)

        {

프림 알고리즘에서는 if((*seek)->GetWeight()>=weight)로 작성하여 새로 들어온 간선의 비중과 같은 부분을 만나면 그 위치에 보관하였습니다. 이번에는 if((*seek)->GetWeight()>weight)로 작성하여 새로 들어온 간선의 비중과 같은 부분을 만나도 다음으로 이동하여 자신보다 처음으로 비중이 큰 간선을 만날 때까지 탐색하세요.

            if((*seek)->GetWeight()>weight)

            {

                break;

            }

        }   

        edges.insert(seek,new Edge(vt1,vt2,weight));

        return true;

    }

    return false;

}

 

그리고 그래프를 병합하는 메서드를 추가하세요.

void Graph::Merge(Graph *graph)

{

입력 인자로 들어온 그래프의 정점 집합에 있는 모든 정점을 추가하세요.

    VIter seek = graph->vertexs.begin();

    VIter last = graph->vertexs.end();

    for(   ;seek != last; ++seek)

    {

        AddVertex(*seek);

    }

마찬가지로 입력 인자로 들어온 그래프의 간선 집합에 있는 모든 간선을 추가하세요.

    EIter eseek = graph->edges.begin();

    EIter elast = graph->edges.end();

   

    for(   ;eseek != elast; ++eseek)

    {

        AddEdge((*eseek)->GetVt1(),(*eseek)->GetVt2(),(*eseek)->GetWeight());

    }

}

 

이제 크루스칼 클래스를 구현합시다. 크루스칼에서는 최소 신장 트리를 만드는 과정에서 분할한 영역이 발생합니다. 여기에서는 분할한 부분들을 관리하기 편하게 그래프의 컬렉션에 보관하게 할게요. 이를 위해 그래프를 보관하는 vector를 Graphs 형식으로 타입 재지정하세요.

typedef vector<Graph *> Graphs;

typedef Graphs::iterator GIter;

 

크루스칼 클래스를 구현합시다.

class Kruscal

{

원본 그래프와 최소 신장 트리를 만드는 과정에서 만들어진 그래프를 보관할 컬렉션이 필요합니다.

    Graph *graph;

    Graphs graphs;

구현하기 쉽게 원본 그래프의 간선 집합을 복사해서 사용할거예요.

    Edges edges;

선택한 간선 개수도 필요하겠죠.

    int secnt;//선택한 간선 개수

public:

생성자는 원본 그래프를 입력 인자로 받습니다.

    Kruscal(Graph *graph);

최소 신장 트리를 만드는 메서드를 제공하세요.

    Graph *MakeMSTree();   

private:

탐욕스런 간선을 선택하였는지 판별하는 메서드를 제공하세요.

    bool SelectEdge();

첫 번째 간선이 탐욕스런 간선인지 판별하는 메서드를 제공하세요.

    bool IsGreedyEdge();

};

 

생성자에서는 입력 인자로 받은 그래프를 멤버 필드에 설정합니다.

Kruscal::Kruscal(Graph *graph)

{

    this->graph = graph;   

}

최소 신장 트리를 만드는 메서드를 구현합시다.

Graph *Kruscal::MakeMSTree()

{

    cout<<"크루스칼 알고리즘 시작"<<endl;

선택한 간선 개수를 0으로 설정하세요.

    secnt = 0;

그래프의 간선 집합을 구하여 멤버 필드에 복사하세요.

    edges = graph->GetEdges();

원본 그래프의 정점 개수-1을 구하세요.

    int v_mone = graph->GetVertexCount()-1;

크루스칼 알고리즘은 탐욕스런 간선을 정점 개수-1 개 선택할 때까지 반복합니다.

    while(secnt < v_mone)

    {

탐욕스런 간선을 선택하게 하고 만약 실패하면 반복문을 탈출하세요.

        if(SelectEdge() == false)

        {

            break;

        }

탐욕스런 간선을 선택하였으면 선택한 간선 개수를 1 증가하세요.

        secnt++;

    }

반복문을 나왔을 때 선택한 간선 개수가 v_mone보다 작으면 제대로 최소 신장 트리를 만들지 못한 것입니다. 메시지를 출력하고 0을 반환하세요.

    if(secnt < v_mone)

    {       

        cout<<"고립 상태의 영역이 있어서 최소 신장 트리를 만들 수 없습니다."<<endl;

        return 0;       

    }

제대로 만들었으면 만드는 과정에서 보관한 그래프 집합의 맨 앞에 최소 신장 트리가 있습니다. 이를 반환하세요.

    return (*graphs.begin());

}

탐욕스런 간선을 선택하는 메서드를 구현하세요.

bool Kruscal::SelectEdge()

{

간선 집합체에 간선이 있으면 선택할 후보가 남아있는 것이므로 반복합니다.

    while(edges.size()>0)

    {

맨 앞의 간선이 탐욕스런 간선인지 판별하는 메서드를 호출하세요.

        if(IsGreedyEdge())

        {

맞다면 참을 반환하세요.

            return true;

        }

    }

만약 간선 집합체에 모든 간선이 탐욕스럽지 않으면 거짓을 반환하세요.

    return false;

}

 

맨 앞의 간선이 탐욕스런 간선인지 판별하는 메서드를 구현합시다.

bool Kruscal::IsGreedyEdge()

{

간선 집합의 맨 앞의 간선을 구하세요.

    Edge *edge = (*edges.begin());

    string vt1 = edge->GetVt1();

    string vt2 = edge->GetVt2();

최소 신장 트리를 남드는 과정에서 생긴 그래프를 보관하는 집합체를 순차적으로 반복해야 합니다.

    GIter seek = graphs.begin();

    GIter last = graphs.end();

    Graph *graph_a=0;

    for(   ;seek != last; ++seek)

    {

만약 간선의 두 정점이 하나의 그래프에 속하면 사이클이 발생하므로 탐욕스런 간선이 아닙니다.

        if((*seek)->Exist(vt1)&&(*seek)->Exist(vt2))

        {

맨 앞의 간선을 제거하세요.

            edges.erase(edges.begin());

            return false;

        }

둘 중에 하나의 정점만 포함하고 있는지 확인하세요.

        if((*seek)->Exist(vt1)||(*seek)->Exist(vt2))

        {

graph_a가 0이면 간선에 포함한 정점이 있는 그래프를 처음 만난 것이므로 기억하게 하세요.

            if(graph_a == 0)

            {

                graph_a = (*seek);

            }

            else

            {

그렇지 않다면 이미 만난 것이므로 간선에 포함한 두 개의 정점을 포함하는 그래프 2개를 찾았으니 반복문을 탈출하세요.

                break;

            }

        }

    }

 

선택한 간선 정보를 출력하세요.

    cout<<"선택한 간선: ";

    edge->View();

    cout<<endl;

graph_a가 0이면 간선에 있는 두 개의 정점 중에 하나라도 포함하는 그래프가 없는 것입니다.

    if(graph_a == 0)

    {

새로운 그래프를 생성한 후에 그래프 집합에 추가하세요.

        graph_a = new Graph();

        graphs.push_back(graph_a);

    }

    else

    {

graph_a가 참이면 seek가 last인지 확인하세요.

        if(seek != last)

        {

seek가 last와 같다면 break 문에 의해 반복문을 탈출한 것이므로 간선에 포함한 두 개의 정점을 포함하는 그래프를 두 개 발견한 것입니다. graph_a와 seek위치의 그래프를 병합하세요.

            graph_a->Merge(*seek);

그리고 seek에 있는 그래프를 소멸하고 그래프 집합에서 제거하세요.

            delete (*seek);

            graphs.erase(seek);

        }

    }

graph_a에 정점과 간선을 추가하세요. Graph 클래스에서는 이미 추가한 정점이면 아무런 작업도 하지 않으므로 두 개의 정점을 모두 추가할게요.

    graph_a->AddVertex(vt1);

    graph_a->AddVertex(vt2);

    graph_a->AddEdge(vt1,vt2,edge->GetWeight());

    return true;

}

 

이제 크루스칼 알고리즘을 테스트 코드를 작성합시다.

int main()

{

그래프를 생성하여 정점과 간선을 추가하는 부분은 같습니다.

    Graph *graph = new Graph();//그래프 동적 생성

    graph->AddVertex("A");

    ...중략...

 

크루스칼을 생성하고 최소 신장 트리를 만드는 메서드를 호출하세요.

    Kruscal *kruscal = new Kruscal(graph);

    Graph *mstree = kruscal->MakeMSTree();

최소 신장 트리가 만들어졌는지 확인하세요.

    if(mstree)

    {

최소 신장 트리의 정보를 출력하세요.

        cout<<"최소 신장 트리 만들기 성공"<<endl;

        mstree->ViewNeighbors();

        delete mstree;

    }

 

    delete kruscal;

    delete graph;

    return 0;

}

 

▷ 실행 결과

=== 이웃 정점 ===

A의 이웃: D E B

B의 이웃: H D A

C의 이웃: D G

D의 이웃: A B C E F H

E의 이웃: F D A

F의 이웃: E D G

G의 이웃: H C F

H의 이웃: B G D

 

크루스칼 알고리즘 시작

선택한 간선: (B,H,2)

선택한 간선: (E,F,2)

선택한 간선: (A,D,3)

선택한 간선: (B,D,3)

선택한 간선: (C,D,3)

선택한 간선: (D,E,3)

선택한 간선: (G,H,3)

최소 신장 트리 만들기 성공

=== 이웃 정점 ===

B의 이웃: H D

H의 이웃: B G

A의 이웃: D

D의 이웃: A B C E

C의 이웃: D

E의 이웃: F D

F의 이웃: E

G의 이웃: H