앞에서 보았듯이 깊이 우선 탐색에서 그래프 탐색은 너비보다는 깊이로 진행한다. 다른 방식으로 미로를 탐색하고 싶다면 노드 0에서 시작하여 노드 4를 방문하러 가기 전에 노드 1, 2, 3을 방문해 보자. 이것은 깊게 들어가는 대신에 망을 넓게 던지는 것을 의미한다. 이러한 탐색 전략을 너비 우선 탐색 또는 간단히 BFS(Breadth-first Search)라고 한다.

너비 우선 탐색에서는 (암묵적이든 실제든) 실타래에 의존할 수 없다. 노드 3과 노드 4는 직접 연결되지 않아서 노드 3에서 노드 4로 갈 수 있는 물리적인 수단이 없으므로 현실 세계에서 미로로 하는 유추는 작동하지 않는다. 너비 우선 탐색이 작동하려면 현재 방문한 노드에서 아직 방문하지 않은 노드에 갈 수 있다고 가정해야 한다. 실제 미로라면 노드 3에서 사라져서 노드 4로 이동할 수 없지만, 노드 4가 존재한다는 것을 안다면 알고리즘에서는 그러한 이동이 가능하다. 이번 버전의 미로 탐색 게임에서는 한 노드에서 알려진 모든 미방문 노드로의 이동이 허용된다.