12.3.1 프림 알고리즘 구현 [디딤돌 자료구조와 알고리즘 with C++]

12.3.1 프림 알고리즘 구현

이제 프림 알고리즘을 구체적으로 구현해 보아요.

프림 알고리즘.zip

 

앞에서 작성했던 그래프 부분까지는 매우 비슷합니다. 먼저 간선을 정의합시다.

class Edge

{

두 개의 정점과 간선의 비용이 필요하죠.

    string vt1;

    string vt2;

    int weight;

public:

생성자는 두 개의 정점과 간선의 비용을 입력 인자로 받습니다.

    Edge(string vt1,string vt2,int height);

특정 정점이 존재하는지 판별하는 메서드를 제공하세요.

    bool Exist(string vt)const;

두 개의 정점을 잇는 간선인지 판별하는 메서드를 제공하세요.

    bool Exist(string vt1, string vt2)const;

하나의 정점을 입력 인자로 받아 다른 나머지 정점을 구하는 메서드를 제공하세요.

    string Other(string vt)const;

간선의 정보를 출력하는 메서드를 제공하세요.

    void View()const;

간선의 비용과 두 개의 정점에 접근하는 메서드를 제공하세요.

    int GetWeight()const;

    string GetVt1()const;

    string GetVt2()const;

};

 

간선 생성자에서는 입력 인자로 받은 값으로 멤버 필드를 설정하세요.

Edge::Edge(string vt1,string vt2,int weight)

{

    this->vt1 = vt1;

    this->vt2 = vt2;

    this->weight = weight;

}

특정 정점이 존재하는지 판별하는 메서드와 두 개의 정점을 잇는 간선인지 판별하는 메서드를 구현하세요.

bool Edge::Exist(string vt)const

{

    return (vt1 == vt)||(vt2==vt);

}

bool Edge::Exist(string vt1, string vt2)const

{

    return Exist(vt1) && Exist(vt2);

}

한 정점을 입력 인자로 받아 나머지 정점을 반환하는 메서드를 구현하세요.

string Edge::Other(string vt)const

{

    if(vt1 == vt)

    {

        return vt2;

    }

    if(vt2 == vt)

    {

        return vt1;

    }

    return "";

}

자신의 정보를 출력하는 메서드를 구현하세요.

void Edge::View()const

{

    cout<<"("<<vt1<<","<<vt2<<","<<weight<<")";

}

간선의 비용과 두 개의 정점에 접근하는 메서드를 구현하세요.

int Edge::GetWeight()const

{

    return weight;

}

string Edge::GetVt1()const

{

    return vt1;

}

string Edge::GetVt2()const

{

    return vt2;

}

 

이번에는 그래프를 구현합시다.

 

먼저 정점 집합과 간선 집합을 vector를 이용하여 형식을 지정하세요.

typedef vector<string> Vertexs;

typedef Vertexs::iterator VIter;

typedef Vertexs::const_iterator CVIter;

 

typedef vector<Edge *> Edges;

typedef Edges::iterator EIter;

typedef Edges::const_iterator CEIter;

 

그래프 클래스도 앞에서 작성했던 것들과 매우 비슷합니다.

class Graph

{

멤버 필드와 정점과 간선의 집합이 필요하겠죠.

    Vertexs vertexs;

    Edges edges;

public:

정점과 간선을 추가하고 존재하는지 판별하는 메서드와 이웃들의 정보를 출력하는 메서드도 제공합시다.

    bool AddVertex(string vt);

    bool Exist(string vt)const;

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

    bool Exist(string vt1,string vt2)const;

    void ViewNeighbors()const;

    void ViewNeighbor(string vt)const;   

정점의 개수를 구하는 메서드를 제공하세요. 프림 알고리즘에서는 원본 그래프에 있는 정점을 선택해 나가는 알고리즘으로 모든 정점을 선택할 때까지 반복합니다. 따라서 그래프의 정점 개수를 알 수 있어야겠죠.

    int GetVertexCount()const;

간선 집합을 구하는 메서드를 제공하세요.

    Edges GetEdges()const;

첫 번째 정점을 구하는 메서드를 제공하세요.

    string GetFirstVertex()const;

};

 

그래프 소멸자에서는 내부에서 생성한 간선들을 해제해 주어야 합니다.

Graph::~Graph(void)

{

    EIter seek = edges.begin();

    EIter last = edges.end();

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

    {

        delete (*seek);//간선 소멸       

    }

}

정점을 추가하는 메서드를 구현하세요. 앞에서 작성했던 부분과 차이가 없습니다.

bool Graph::AddVertex(string vt)

{

    if(Exist(vt))

    {

        return false;

    }

    vertexs.push_back(vt);

    return true;

}

정점이 존재하는 메서드도 구현하세요. 앞에서 작성했던 부분과 차이가 없습니다.

bool Graph::Exist(string vt)const

{

    return find(vertexs.begin(),vertexs.end(),vt) != vertexs.end();

}

 

간선을 추가하는 메서드도 구현하세요. 앞에서 작성했던 부분과 차이가 없습니다.

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)

            {

                break;

            }

        }

탐색한 위치에 새로운 간선을 생성하여 추가하세요.

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

        return true;

    }

    return false;

}

 

두 개의 정점을 포함하는 간선이 있는지 판별하는 메서드를 구현하세요. 앞에서 작성했던 부분과 차이가 없습니다.

bool Graph::Exist(string vt1,string vt2)const

{

    CEIter seek = edges.begin();

    CEIter last = edges.end();

 

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

    {

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

        {

            return true;

        }

    }   

    return false;

}

 

이웃 정점들을 출력하는 메서드를 구현하세요. 앞에서 작성했던 부분과 차이가 없습니다.

void Graph::ViewNeighbors()const

{

    cout<<"=== 이웃 정점 ==="<<endl;

    CVIter seek = vertexs.begin();

    CVIter last = vertexs.end();

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

    {

        cout<<(*seek)<<"의 이웃: ";

        ViewNeighbor(*seek);//i정점의 이웃 보여주기

    }

    cout<<endl;

}

void Graph::ViewNeighbor(string vt)const

{

    CEIter seek = edges.begin();

    CEIter last = edges.end();

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

    {

        if((*seek)->Exist(vt))

        {

            cout<<(*seek)->Other(vt)<<" ";

        }

    }

    cout<<endl;

}

 

정점의 개수를 구하는 메서드를 구현하세요.

int Graph::GetVertexCount()const

{

    return vertexs.size();

}

 

간선 집합을 구하는 메서드를 구현하세요.

Edges Graph::GetEdges()const

{

    return edges;

}

 

첫 번째 정점을 구하는 메서드를 구현하세요.

string Graph::GetFirstVertex()const

{

정점이 하나도 없으면 빈 문자열을 반환하세요.

    if(vertexs.size()==0)

    {

        return "";

    }

    return vertexs[0];

}

 

이제 프림 알고리즘을 구현합시다.

class Prim

{

멤버로 원본 그래프가 필요합니다. 편의상 원본 그래프의 간선 집합도 멤버로 기억하는 멤버도 추가합시다.

    Graph *graph;

    Edges edges;

public:

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

    Prim(Graph *graph);

    ~Prim();

최소 신장 트리를 만드는 메서드를 제공해야죠.

    Graph * MakeMSTree();

private:

프림 알고리즘에서는 탐욕적인 방법으로 정점을 선택하면서 최소 신장 트리를 만듭니다. 만약 그래프의 고립 영역이 있으면 탐욕적인 방법으로 모든 정점을 선택하지 못할 수 있습니다. 탐욕적인 방법으로 정점을 선택하여 최소 신장 트리에 추가하는 메서드를 추가하세요. 반환 형식은 선택 여부를 반환하게 합시다.

    bool SelectVertex(Graph *mstree);

현재 간선에 끝점 중에 탐욕적인 정점인지 판별하고 정점 이름을 반환하는 메서드를 제공하세요.

    string IsGreedyVertex(Edge *edge,Graph *mstree)const;

};

 

생성자에서는 원본 그래프를 입력받아 멤버에 설정하세요.

Prim::Prim(Graph *graph)

{

    this->graph = graph;

}

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

Graph *Prim::MakeMSTree()

{

    cout<<"프림 알고리즘 시작"<<endl;

비어있는 최소 신장 트리를 생성하세요.

    Graph *mstree = new Graph();

원본 그래프의 첫번째 정점을 선택하세요. 프림 알고리즘에서는 처음 선택하는 정점은 무엇을 선택하든 관계 없습니다.

    string start = graph->GetFirstVertex();

    cout<<start<<endl;

    mstree->AddVertex(graph->GetFirstVertex());

편의를 위해 원본 그래프의 간선 집합과 정점 개수를 구하세요.

    edges = graph->GetEdges();

    int vcnt = graph->GetVertexCount();

 

탐욕 알고리즘에서는 최소 신장 트리에 탐욕스런 방법으로 정점을 하나씩 추가합니다. 물론 원본 그래프의 정점 개수만큼 선택해야겠죠.

    while(mstree->GetVertexCount() < vcnt)

    {

만약 원본 그래프에 고립 상태인 영역이 있으면 탐욕스런 방법으로 모든 정점을 선택할 수가 없습니다. 따라서 탐욕스런 방법으로 정점을 선택하였는지 판별하는 부분이 필요합니다.

        if(SelectVertex(mstree) == false)

        {

            break;

        }

    }

 

만약 반복문을 탈출한 상태에서 최소 신장 트리의 정점 개수가 원본 그래프의 정점 개수보다 작으면 고립 상태의 영역이 있어서 최소 신장 트리를 만들 수 없는 것입니다. 이 때 메시지를 출력하고 0을 반환하세요.

    if(mstree->GetVertexCount() <vcnt)

    {

        delete mstree;

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

        return 0;       

    }

 

이 부분에 도달했다면 최소 신장 트리에 정점 개수가 원본 그래프의 정점 개수와 같을 때입니다. 생성한 최소 신장 트리를 반환하세요.

    return mstree;

}

 

탐욕스런 방법으로 정점을 선택하여 최소 신장 트리에 추가하는 메서드를 구현합시다.

bool Prim::SelectVertex(Graph *mstree)

{

원본 그래프의 정점을 순회하면서 탐욕스런 방법에 적합한 정점을 찾습니다. 여기에서 간선은 비용 순으로 배치한 상태이므로 탐욕스런 방법으로 발견한 첫 번째 정점만 찾아 추가합니다.

    EIter seek = edges.begin();

    EIter last = edges.end();

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

    {

현재 간선에 탐욕스런 정점이 있는지 판별하는 메서드를 호출하세요.

        string next_vtx = IsGreedyVertex(*seek,mstree);

        if(next_vtx != "")

        {

만약 탐욕스런 정점이면 정보를 출력하세요.

            string other =(*seek)->Other(next_vtx);

            int weight = (*seek)->GetWeight();

            cout<<"("<<other<<","<<next_vtx<<":"<<weight<<")"<<endl;

그리고 선택한 정점을 추가하고 간선도 추가하세요.

            mstree->AddVertex(next_vtx);

            mstree->AddEdge(next_vtx, other,weight);

            return true;

        }       

    }

    return false;

}

 

이제 특정 간선의 끝 점중에 최소 신장 트리에 탐욕스런 방법으로 선택할 정점이 있는지 판별하는 메서드를 구현합시다.

string Prim::IsGreedyVertex(Edge *edge,Graph *mstree)const

{

먼저 간선의 두 개의 끝점을 구하세요.

    string vtx1 = edge->GetVt1();

    string vtx2 = edge->GetVt2();

만약 하나의 정점만 포함하고 있다면 나머지 정점이 탐욕스런 방법으로 선택할 정점입니다. 만약 하나도 포함하고 있지 않다면 현재까지의 최소 신장 트리의 정정들 중에 갈 수 있는 경로가 없는 것이라 선택할 정점이 없습니다. 그리고 둘 다 포함하고 있다면 사이클이 만들어져서 선택하지 말아야 합니다.

    if(mstree->Exist(vtx1))

    {

        if(mstree->Exist(vtx2))

        {

둘 다 포함하고 있을 때이므로 빈 문자열을 반환하세요.

            return "";

        }

vtx1은 포함하고 있고 vtx2가 없으므로 vtx2를 선택합니다.

        return vtx2;

    }

    if(mstree->Exist(vtx2))

    {

vtx1은 없고 vtx2만 있으므로 vt1을 선택합니다.

        return vtx1;

    }

둘 다 없을 때이므로 빈 문자열을 반환하세요.

    return "";

}

 

이제 프림 알고리즘을 이용하여 최소 신장 트리를 만드는 예제 코드르 작성합시다.

int main()

{

그래프를 생성하세요.

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

 

테스트에 사용할 그래프에 정점을 추가하세요.

    graph->AddVertex("A");

    graph->AddVertex("B");

    graph->AddVertex("C");

    graph->AddVertex("D");

    graph->AddVertex("E");

    graph->AddVertex("F");

    graph->AddVertex("G");

    graph->AddVertex("H");

 

간선도 추가하세요.

    graph->AddEdge("A","B",5);

    graph->AddEdge("A","D",3);

    graph->AddEdge("A","E",4);

    graph->AddEdge("B","D",3);

    graph->AddEdge("B","H",2);

    graph->AddEdge("C","D",3);

    graph->AddEdge("C","G",4);

    graph->AddEdge("D","H",5);

    graph->AddEdge("D","E",3);

    graph->AddEdge("D","F",3);

    graph->AddEdge("E","F",2);

    graph->AddEdge("F","G",6);

    graph->AddEdge("G","H",3);

 

원본 그래프의 정보를 출력하세요.

    graph->ViewNeighbors();

 

프림 알고리즘을 생성하세요.

    Prim *prim = new Prim(graph);

최소 신장 트리를 만들 것을 요청합니다.

    Graph *mstree = prim->MakeMSTree();

    if(mstree)

    {

반환받은 최소 신장 트리가 존재하면 성공을 출력하고 최소 신장 트리 정보를 출력하세요.

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

        mstree->ViewNeighbors();

        delete mstree;

    }

    delete prim;

    delete graph;

    return 0;

}

 

▷ 실행 결과

=== 이웃 정점 ===

A의 이웃: D E B

B의 이웃: H D A

C의 이웃: D G

D의 이웃: F E C B A H

E의 이웃: F D A

F의 이웃: E D G

G의 이웃: H C F

H의 이웃: B G D

 

프림 알고리즘 시작

A

(A,D:3)

(D,F:3)

(F,E:2)

(D,C:3)

(D,B:3)

(B,H:2)

(H,G:3)

최소 신장 트리 만들기 성공

=== 이웃 정점 ===

A의 이웃: D

D의 이웃: B C F A

F의 이웃: E D

E의 이웃: F

C의 이웃: D

B의 이웃: H D

H의 이웃: B G

G의 이웃: H

 

이상으로 프림 알고리즘을 이용하여 최소 신장 트리를 만드는 코드를 구현하였습니다. 여기에서 작성한 프림 알고리즘은 몇 가지 개선할 사항이 있습니다.

 

제일 먼저 개선할 사항은 탐욕스런 정점을 선택하는 과정에서 특정 간선의 두 개의 정점이 현재까지 만든 최소 신장 트리에 포함하고 있다면 해당 간선은 다음 선택 과정에서는 확인할 필요가 없습니다. 따라서 이럴 때 간선 집합에서 제거한다면 보다 나은 성능을 발휘할 수 있습니다.

 

이 외에도 몇 가지 개선 사항이 있습니다. 여러분께서 보다 나은 탐욕 알고리즘을 구현하고자 한다면 무엇을 개선하면 좋을 지 고민하시고 수정해 보세요.

12.3 프림 알고리즘 [디딤돌 자료구조와 알고리즘 with C++]

12.3.2 프림 알고리즘 소스 코드 [디딤돌 자료구조와 알고리즘 with C++]