백트랙

 

다음 전체탐색을 위한 백트랙을 진행하면서 이전 전체탐색의 흔적을 지워야 한다는 것이다.

 

너비우선탐색은 백트랙을 하지 않는다. 대신에 현재 정점에서 깊이가 1인 정점을 모두 방문해야 하므로 큐(queue)라는 선입선출(FIFO) 자료구조를 활용하여 현재 정점에서 깊이가 1 더 깊은 모든 정점을 순차적으로 큐에 저장하여 탐색에 

활용한다.