제일 먼저 인접 행렬로 너비 우선 탐색을 구현해 보아요.
그래프와 Heuristic에 관한 코드는 10.3.3 깊이 우선 탐색(인접 행렬) 코드와 같으니 참고하세요.
먼저 깊이 우선 탐색하는 순서를 이해하기 쉽게 구현한 코드를 구현합시다.
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();
너비 우선 탐색은 큐를 이용합니다.
queue<Heuristic *> hq;
초기 경험 정보를 생성하여 큐에 보관하세요.
Heuristic *heu = new Heuristic(graph,0,8);//초기 경험 정보를 생성
hq.push(heu);//큐에 보관
큐가 빌 때까지 반복합니다.
while(hq.empty() == false) //반복(큐가 비어 있지 않다면)
{
큐에서 경험 정보를 꺼내오세요.
heu = hq.front();//큐에서 경험 정보 꺼내옮
hq.pop();
목적지에 도달하였는지 찾는 중인지 출력하세요.
만약 최단 거리를 찾았을 때 더 이상 작업을 진행하기 원하지 않는다면 반복문 탈출하는 구문을 사용하는 형태로 수정하세요. 여기에서는 큐가 빌 때까지 전수 조사하기로 할게요.
if(heu->IsGoal())//목적지에 도달하면
{
cout<<"===== 솔루션 ";
}
else
{
cout<<"찾는중 ";
}
현재까지 방문한 경로를 출력하세요.
heu->View();
EnumNext 메서드에서는 현재 경험의 마지막 방문한 정점에서 경험하지 않은 이웃 정점을 추가 방문하는 다음 경험을 생성하여 반환하는 작업을 수행합니다.
Heues nheues = heu->EnumNext();//큐에서 꺼내온 경험 정보에서 다음 경험 목록 조사
HIter seek = nheues.begin();
HIter last = nheues.end();
for( ;seek != last; ++seek)//반복(다음 경험 목록을 순차적으로 반복)
{
조사한 다음 경험 목록을 큐에 보관하세요.
hq.push(*seek);//큐에 보관
}
더 이상 필요없는 경험을 소멸하세요.
delete heu;
}
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 1 찾는중 Foots: 0 2 찾는중 Foots: 0 1 2 찾는중 Foots: 0 1 3 찾는중 Foots: 0 2 1 찾는중 Foots: 0 2 4 찾는중 Foots: 0 1 2 4 찾는중 Foots: 0 1 3 6 찾는중 Foots: 0 2 1 3 찾는중 Foots: 0 2 4 5 찾는중 Foots: 0 2 4 6 찾는중 Foots: 0 2 4 7 찾는중 Foots: 0 1 2 4 5 찾는중 Foots: 0 1 2 4 6 찾는중 Foots: 0 1 2 4 7 찾는중 Foots: 0 1 3 6 4 ===== 솔루션 Foots: 0 1 3 6 8 찾는중 Foots: 0 2 1 3 6 찾는중 Foots: 0 2 4 6 3 ===== 솔루션 Foots: 0 2 4 6 8 찾는중 Foots: 0 1 2 4 6 3 ===== 솔루션 Foots: 0 1 2 4 6 8 찾는중 Foots: 0 1 3 6 4 2 찾는중 Foots: 0 1 3 6 4 5 찾는중 Foots: 0 1 3 6 4 7 찾는중 Foots: 0 2 1 3 6 4 ===== 솔루션 Foots: 0 2 1 3 6 8 찾는중 Foots: 0 2 4 6 3 1 찾는중 Foots: 0 2 1 3 6 4 5 찾는중 Foots: 0 2 1 3 6 4 7
다음은 현재 경험에서 다음 경험을 조사한 후에 바로 목적지에 도달하였는지 확인하는 형태로 코드를 수행한 예제입니다.
int main()
{
Graph *graph = new Graph(9);//그래프 동적 생성
graph->AddEdge(0, 1);//간선 추가
...중략...
graph->ViewNeighbors();
queue<Heuristic *> hq;
Heuristic *heu = new Heuristic(graph,0,8);//초기 경험 정보를 생성
hq.push(heu);//큐에 보관
while(hq.empty() == false) //반복(큐가 비어 있지 않다면)
{
heu = hq.front();//큐에서 경험 정보 꺼내옮
hq.pop();
cout<<"찾는중 ";
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
{
hq.push(*seek);//큐에 보관
}
}
delete heu;
}
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 1 찾는중 Foots: 0 2 찾는중 Foots: 0 1 2 찾는중 Foots: 0 1 3 찾는중 Foots: 0 2 1 찾는중 Foots: 0 2 4 찾는중 Foots: 0 1 2 4 찾는중 Foots: 0 1 3 6 ===== 솔루션 Foots: 0 1 3 6 8 찾는중 Foots: 0 2 1 3 찾는중 Foots: 0 2 4 5 찾는중 Foots: 0 2 4 6 ===== 솔루션 Foots: 0 2 4 6 8 찾는중 Foots: 0 2 4 7 찾는중 Foots: 0 1 2 4 5 찾는중 Foots: 0 1 2 4 6 ===== 솔루션 Foots: 0 1 2 4 6 8 찾는중 Foots: 0 1 2 4 7 찾는중 Foots: 0 1 3 6 4 찾는중 Foots: 0 2 1 3 6 ===== 솔루션 Foots: 0 2 1 3 6 8 찾는중 Foots: 0 2 4 6 3 찾는중 Foots: 0 1 2 4 6 3 찾는중 Foots: 0 1 3 6 4 2 찾는중 Foots: 0 1 3 6 4 5 찾는중 Foots: 0 1 3 6 4 7 찾는중 Foots: 0 2 1 3 6 4 찾는중 Foots: 0 2 4 6 3 1 찾는중 Foots: 0 2 1 3 6 4 5 찾는중 Foots: 0 2 1 3 6 4 7