10.3.3 깊이 우선 탐색(인접 행렬) 코드

여기에서는 방향성 없는 그래프에서 깊이 우선 탐색 알고리즘을 구현한 소스를 소개할게요.

참고로  Graph 클래스의 AddEdge에서 start에서 goal로 가는 행열만 1로 설정하면 방향성 있는 그래프입니다.

void Graph::AddEdge(int start, int goal)//간선 추가

{

    matrix[start][goal] = 1;//간선 설정

}

다음은 앞에서 작성한 인접 행렬로 구현한 그래프와 이를 이용한 깊이 우선 탐색 소스 코드입니다.

//Graph.h
#pragma once
#include <iostream>
#include <vector>
using namespace std;
typedef vector<int> Neighbors;
class Graph
{
    const int vn;//정점의 개수
    int **matrix;//인접 행렬    
public:
    Graph(int vn);
    ~Graph(void);    
    void AddEdge(int start, int goal);//간선 추가
    void ViewNeighbors()const;
    void ViewNeighbor(int vt)const;
    Neighbors FindNeighbors(int vt);
};

//Graph.cpp
#include "Graph.h"
#include <string.h>
Graph::Graph(int vn):vn(vn)
{
    matrix = new int *[vn];//매트릭스 메모리 할당
     for (int i = 0; i < vn; i++)
     {
         matrix[i] = new int[vn];//매트릭스 [i-row] 메모리 할당
         memset(matrix[i], 0, sizeof(int)*vn);//메모리 0으로 초기화
     }
}
Graph::~Graph(void)
{
    for (int i = 0; i < vn; i++)
    {
        delete[] matrix[i];//매트릭스 [i-row]  메모리 소멸
    }
    delete[] matrix;//매트릭스 메모리 해제
}
void Graph::AddEdge(int start, int goal)//간선 추가
{
    matrix[start][goal] = 1;//간선 설정
    //다음 코드를 주석 처리하면 방향성 있는 그래프
    matrix[goal][start] = 1;//간선 설정
}

void Graph::ViewNeighbors()const
{
    cout<<"=== 이웃 정점 ==="<<endl;
    for (int i = 0; i < vn; i++)
    {
        cout<<i<<"의 이웃: ";
        ViewNeighbor(i);//i정점의 이웃 보여주기
    }
    cout<<endl;
}

void Graph::ViewNeighbor(int vt)const
{
    for (int i = 0; i < vn; i++)
    {
        if(matrix[vt][i])
        {
            cout<<i<<" ";
        }
    }
    cout<<endl;
}

Neighbors Graph::FindNeighbors(int vt)
{
    Neighbors neighbors;
    for (int i = 0; i < vn; i++)
     {
         if(matrix[vt][i])
         {
             neighbors.push_back(i);
         }
     }
    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());//가장 최근에 방문한 정점
    Neighbors 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(9);//그래프 동적 생성

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