CH14-3 그래프의 탐색(6)

14-3. 그래프의 탐색 ⑥

이번에는 너비우선 탐색의 구현모델부터 알아보자.

이친구는 큐를 갖고 구현한다고 전에 이야기했었다.

지율에서 연락이 출발하면… 우선 민석과 동수에게 연락을 취한다. 그럼 다음 연락을 취할 기회를 가진 친구는 동수와 민석이므로, 이 친구들이 기회를 갖고 있다는 것을 어딘가에 저장해서 알아야 한다. 이때 어울리는 자료구조가 바로 큐이다.

즉 너비우선탐색에서는, 연락받은 정점들은 큐에 enqueue된다!

동수와 민석 중 누구를 먼저 enqueue할것인지는 크게 중요하지 않다.

잠깐… 그전에 문제 14-2를 풀어보며 느낀점을 적으려고 한다.

• 보기

다시 강의로 돌아가자.

민석과 동수가 큐에 enqueue되고 나면, 하나씩 dequeue되면서 디큐된 정점이 다시 주변에 연락할 기회를 얻는다.

1. 연락을 받으면, 큐에 enqueue된다.
2. 연락이 끝나면, 큐에서 dequeue된 정점이 다시 주변에 연락을 취한다.
3. 이때 연락받은 다수의 정점중, 큐에 enqueue되는 순서는… 연결리스트 순서대로 들어가는게 구현에 편리할 것이다.(LFisrt와 LNext 이용..)

위의 순서만 반복해도 모든 정점에 연락을 취할 수 있다는 것을 알 수 있다!