10.4 깊이 우선 탐색(정점과 간선 그래프)

10.4 깊이 우선 탐색(정점과 간선 그래프)

깊이우선탐색(정점과 간선 그래프).zip

이번에는 그래프를 정점(Vertex)과 간선(Edge) 집합으로 표현한 후에 깊이 우선 탐색을 구현해 보아요.

 

먼저 간선을 정의합시다. 여기에서는 방향성 없는 그래프로 표현할게요.

class Edge

{

간선의 두 정점을 멤버 필드로 추가하세요.

    int vt1;

    int vt2;

public:

생성할 때 두 개의 정점을 입력 인자로 받습니다.

    Edge(int vt1,int vt2);

특정 점정을 포함하는지 판별하는 메서드를 제공하세요.

    bool Exist(int vt)const;

두 개의 정점을 포함하는지 판별하는 메서드도 제공하세요.

    bool Exist(int vt1, int vt2)const;

하나의 정점을 입력 인자로 받은 후에 나머지 정점을 반환하는 메서드도 제공하세요.

    int Other(int vt)const;

간선 정보를 출력하는 메서드도 제공합시다.

    void View()const;

};

 

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

Edge::Edge(int vt1,int vt2)

{

    this->vt1 = vt1;

    this->vt2 = vt2;

}

 

정점을 포함하는지 판별하는 메서드를 구현하세요.

bool Edge::Exist(int vt)const

{

vt1 혹은 vt2와 같으면 포함하는 것이죠.

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

}

 

두 개의 정점을 모두 포함하는지 판별하는 메서드를 구현하세요.

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

{

vt1 정점과 vt2 정점이 존재하는지 확인한 결과를 반환하세요.

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

}

 

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

int Edge::Other(int vt)const

{

    if(vt1 == vt)

    {

        return vt2;

    }

    if(vt2 == vt)

    {

        return vt1;

    }

    return -1;

}

 

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

void Edge::View()const

{

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

}

 

이제 Graph 클래스를 구현합시다. 제공할 기능은 인접 행렬로 구현한 그래프와 비슷하겠죠.

 

먼저 정점의 집합을 Vertexs로 타입 재지정하세요.

typedef vector<int> Vertexs;

typedef Vertexs::iterator VIter;

typedef Vertexs::const_iterator CVIter;

 

Edge *의 집합을 Edges로 타입 재지정하세요.

typedef vector<Edge *> Edges;

typedef Edges::iterator EIter;

typedef Edges::const_iterator CEIter;

 

class Graph

{

그래프에는 정점의 집합인 Vertexs 형식 멤버와 간선의 집합인 Edges 형식 멤버가 필요합니다.

    Vertexs vertexs;

    Edges edges;

public:   

    ~Graph(void);

정점을 추가하는 메서드를 제공하세요.

    bool AddVertex(int vt);

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

    bool Exist(int vt)const;

간선을 추가하는 메서드를 제공하세요.

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

두 정점을 끝점으로 하는 간선이 존재하는지 판별하는 메서드도 제공하세요.

    bool Exist(int vt1,int vt2)const;

모든 정점의 이웃들을 출력하는 메서드를 제공합시다.

    void ViewNeighbors()const;

특정 정점의 이웃들을 출력하는 메서드를 제공합시다.

    void ViewNeighbor(int vt)const;

특정 정점의 이웃을 조사하는 메서드를 제공합시다.

    Vertexs FindNeighbors(int vt);

};

 

소멸자를 먼저 구현하기로 해요.

Graph::~Graph(void)

{

그래프 내에서 간선을 동적으로 생성합니다. 그래프의 소멸자에서는 간선 집합에 보관하고 있는 간선들을 소멸하세요.

    EIter seek = edges.begin();

    EIter last = edges.end();

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

    {

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

    }   

}

 

정점을 추가하는 메서드를 구현합시다.

bool Graph::AddVertex(int vt)

{

먼저 정점이 존재하는지 확인하세요. 존재하면 추가하지 않고 거짓을 반환합니다.

    if(Exist(vt))

    {

        return false;

    }

존재하지 않을 때 정점 집합에 추가하세요.

    vertexs.push_back(vt);

    return true;

}

 

정점이 존재하는지 판별하는 메서드를 구현하세요.

bool Graph::Exist(int vt)const

{

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

}

간선을 추가하는 메서드를 구현하세요.

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

{

먼저 두 개의 정점을 포함하는지 확인하세요.

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

    {

그리고 두 개의 정점을 잇는 간선이 이미 있는지 확인하여 이미 있다면 거짓을 반환하세요.

        if(Exist(vt1,vt2))

        {

            return false;

        }

없을 때 간선을 생성하여 간선 집합에 추가한 후에 참을 반환하세요.

        edges.push_back(new Edge(vt1,vt2));

        return true;

    }

두 개의 정점이 모두 포함하고 있지 않을 때 거짓을 반환하세요.

    return false;

}

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

bool Graph::Exist(int vt1,int 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(int vt)const

{

간선 집합을 순차적으로 순회하세요.

    CEIter seek = edges.begin();

    CEIter last = edges.end();

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

    {

간선에 입력 인자로 받은 정점이 존재하면 다른 나머지 정점을 출력하세요.

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

        {

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

        }

    }

    cout<<endl;

}

 

같은 방법으로 특정 정점의 이웃하는 정정 집합을 구하는 메서드를 구현하세요.

Vertexs Graph::FindNeighbors(int vt)

{

    Vertexs neighbors;

    EIter seek = edges.begin();

    EIter last = edges.end();

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

    {

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

        {

간선에 입력 인자로 받은 정점이 존재하면 다른 나머지 정점을 이웃 정점 집합에 추가하세요.

            neighbors.push_back((*seek)->Other(vt));

        }

    }   

    return neighbors;

}

 

 

경험 정보 클래스는 인접 행렬을 이용한 깊이 우선 탐색의 코드와 차이가 없습니다. 10.3.3 을 참고하세요.

 

진입점 main에서도 그래프를 동적 생성하여 정점을 추가하는 앞부분만 차이가 있을 뿐 간선 추가부터는 똑같습니다.

int main()

{

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

    for(int i = 0; i<=8;i++)

    {

        graph->AddVertex(i);

    }

    ...중략...

    return 0;

}

 

다음은 테스트에 사용한 그래프입니다.

▷ 실행 결과

=== 이웃 정점 ===

0의 이웃: 1 2

1의 이웃: 0 2 3

2의 이웃: 0 1 4

3의 이웃: 1 6

4의 이웃: 2 5 6 7

5의 이웃: 4

6의 이웃: 3 4 8

7의 이웃: 4

8의 이웃: 6

 

Foots: 0

Foots: 0 2

Foots: 0 2 4

Foots: 0 2 4 7

Foots: 0 2 4 6

솔루션 Foots: 0 2 4 6 8

Foots: 0 2 4 6 3

Foots: 0 2 4 6 3 1

Foots: 0 2 4 5

Foots: 0 2 1

Foots: 0 2 1 3

Foots: 0 2 1 3 6

솔루션 Foots: 0 2 1 3 6 8

Foots: 0 2 1 3 6 4

Foots: 0 2 1 3 6 4 7

Foots: 0 2 1 3 6 4 5

Foots: 0 1

Foots: 0 1 3

Foots: 0 1 3 6

솔루션 Foots: 0 1 3 6 8

Foots: 0 1 3 6 4

Foots: 0 1 3 6 4 7

Foots: 0 1 3 6 4 5

Foots: 0 1 3 6 4 2

Foots: 0 1 2

Foots: 0 1 2 4

Foots: 0 1 2 4 7

Foots: 0 1 2 4 6

솔루션 Foots: 0 1 2 4 6 8

Foots: 0 1 2 4 6 3

Foots: 0 1 2 4 5

 

다음은 전체 코드입니다.

//Edge.h

#pragma once

class Edge

{

    int vt1;

    int vt2;

public:

    Edge(int vt1,int vt2);

    bool Exist(int vt)const;

    bool Exist(int vt1, int vt2)const;

    int Other(int vt)const;

    void View()const;

};

 

//Edge.cpp

#include "Edge.h"

#include <iostream>

using namespace std;

 

Edge::Edge(int vt1,int vt2)

{

    this->vt1 = vt1;

    this->vt2 = vt2;

}

 

bool Edge::Exist(int vt)const

{

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

}

 

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

{

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

}

 

int Edge::Other(int vt)const

{

    if(vt1 == vt)

    {

        return vt2;

    }

 

    if(vt2 == vt)

    {

        return vt1;

    }

 

    return -1;

}

 

void Edge::View()const

{

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

}

 

 

 

//Graph.h

#pragma once

#include "Edge.h"

#include <iostream>

#include <vector>

using namespace std;

typedef vector<int> 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:   

    ~Graph(void);   

    bool AddVertex(int vt);

    bool Exist(int vt)const;

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

    bool Exist(int vt1,int vt2)const;

    void ViewNeighbors()const;

    void ViewNeighbor(int vt)const;

    Vertexs FindNeighbors(int vt);

};

 

//Graph.cpp

#include "Graph.h"

#include <string.h>

#include <algorithm>

 

Graph::~Graph(void)

{

    EIter seek = edges.begin();

    EIter last = edges.end();

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

    {

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

    }   

}

bool Graph::AddVertex(int vt)

{

    if(Exist(vt))

    {

        return false;

    }

    vertexs.push_back(vt);

    return true;

}

 

bool Graph::Exist(int vt)const

{

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

}

 

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

{

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

    {

        if(Exist(vt1,vt2))

        {

            return false;

        }

        edges.push_back(new Edge(vt1,vt2));

        return true;

    }

    return false;

}

 

bool Graph::Exist(int vt1,int 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(int vt)const

{

    CEIter seek = edges.begin();

    CEIter last = edges.end();

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

    {

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

        {

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

        }

    }

    cout<<endl;

}

 

Vertexs Graph::FindNeighbors(int vt)

{

    Vertexs neighbors;

    EIter seek = edges.begin();

    EIter last = edges.end();

 

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

    {

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

        {

            neighbors.push_back((*seek)->Other(vt));

        }

    }   

    return neighbors;

}

 

//Heuristic.h

#pragma once

#include "Graph.h"

#include <vector>

using namespace std;

 

typedef vector<int> Foots;

typedef Foots::iterator FIter;

typedef Foots::const_iterator CFIter;

 

class Heuristic;

typedef vector<Heuristic *> Heues;

typedef Heues::iterator HIter;

typedef Heues::const_iterator CHIter;

 

class Heuristic

{

    Graph *graph;   

    int goal;

    Foots foots;

public:

    Heuristic(Graph *graph, int start,int goal);   

    Heues EnumNext();

    bool IsGoal()const;

    void View()const;   

private:

    Heuristic(const Heuristic *bheu,int vt);

};

 

//Heuristic.cpp

#include "Heuristic.h"

#include <algorithm>

 

Heuristic::Heuristic(Graph *graph,int start,int goal)

{

    this->graph = graph;

    foots.push_back(start);

    this->goal = goal;

}

 

 

 

 

Heues Heuristic::EnumNext()

{

    Heues nheues;

    int last_foot = (*foots.rbegin());//가장 최근에 방문한 정점

    Vertexs neighbors = graph->FindNeighbors(last_foot);//마지막 방문 정점의 이웃하는 정점을 구함

    FIter seek = neighbors.begin();

    FIter last = neighbors.end();

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

    {

        if(find(foots.begin(), foots.end(),*seek) == foots.end())//방문한 적이 없으면

        {

            nheues.push_back(new Heuristic(this,*seek));//*seek를 추가 방문하는 새로운 경험을 생성

        }           

    }

    return nheues;

}

 

bool Heuristic::IsGoal()const

{

    return (*foots.rbegin()) == goal;

}

 

void Heuristic::View()const

{

    cout<<"Foots: ";

    CFIter seek = foots.begin();

    CFIter last = foots.end();

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

    {

        cout<<(*seek)<<" ";

    }

    cout<<endl;

}

 

Heuristic::Heuristic(const Heuristic *bheu,int vt)

{

    this->graph = bheu->graph;

    foots = bheu->foots;

    this->goal = bheu->goal;

 

    foots.push_back(vt);//vt를 방문한 행적에 추가

}

 

//Program.cpp

#include "Heuristic.h"

#include <stack>

using namespace std;

int main()

{

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

    for(int i = 0; i<=8;i++)

    {

        graph->AddVertex(i);

    }

 

    graph->AddEdge(0, 1);//간선 추가

    graph->AddEdge(0, 2);//간선 추가

    graph->AddEdge(1, 2);//간선 추가

    graph->AddEdge(1, 3);//간선 추가

    graph->AddEdge(2, 4);//간선 추가

    graph->AddEdge(3, 6);//간선 추가

    graph->AddEdge(4, 5);//간선 추가

    graph->AddEdge(4, 6);//간선 추가

    graph->AddEdge(4, 7);//간선 추가

    graph->AddEdge(6, 8);//간선 추가

    graph->ViewNeighbors();

   

    stack<Heuristic *> hs;

   

    Heuristic *heu = new Heuristic(graph,0,8);//초기 경험 정보를 생성

    hs.push(heu);//스택에 보관

    while(hs.empty() == false) //반복(스택이 비어 있지 않다면)

    {

        heu = hs.top();//스택에서 경험 정보 꺼내옮

        hs.pop();

        heu->View();

        Heues nheues = heu->EnumNext();//스택에서 꺼내온 경험 정보에서 다음 경험 목록 조사

        HIter seek = nheues.begin();

        HIter last = nheues.end();

        for(  ;seek != last; ++seek)//반복(다음 경험 목록을 순차적으로 반복)

        {

            if((*seek)->IsGoal())//목적지에 도달하면

            {

                cout<<"솔루션 ";

                (*seek)->View();//결과 출력

                delete (*seek);

            }

            else//그렇지 않다면

            {

                hs.push(*seek);//스택에 보관

            }

        }

        delete heu;

    }

    return 0;

}

 

여기에서는 간선의 무게(비중 혹은 비용, weight)나 정점의 이름을 부여하지는 않았습니다. 다음에 너비 우선 탐색을 하면서 간선의 무게나 정점의 이름을 부여하는 그래프도 다루기로 할게요.

 

그리고 이 책에서는 최소 신장 트리를 다루면서 다시 그래프를 이용할 거예요. 이번 장에서는 그래프를 이용한 깊이 우선 탐색 알고리즘은 동적 알고리즘으로 구현하 수 있다는 것에 초점을 두었습니다.

 

원본 그래프와 출발지, 목적지를 설정한 초기 경험 정보를 생성

스택에 보관

반복(스택이 비어 있지 않다면)

    스택에서 경험 정보 꺼내옮

    스택에서 꺼내온 경험 정보에서 다음 경험(이웃을 방문하는) 목록 조사

    반복(다음 경험 목록을 순차적으로 반복)

        목적지에 도달하면

            결과 출력

        그렇지 않다면

            스택에 보관