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