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

이번에는 그래프를 정점(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;

Graph 클래스를 정의합시다.

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); 
};

Grpah 소스 코드를 작성합시다. 먼저 소멸자를 먼저 구현하기로 해요.

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