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