미로 탐색(exploring the labyrinth)은 오래된 문제다. 이 문제의 시작은 크레타의 미노스(Minos) 왕이 전쟁에서 진 아테네 왕에게 7년마다 남녀 각각 7명을 크레타로 보내게 한 이야기로 거슬러 올라간다. 크레타로 온 남녀는 사람의 몸과 황소의 머리를 한 괴물인 미노타우로스(Minotaur)가 사는 미궁에 던져졌다. 이 미궁은 매우 복잡한 미로여서 불운한 희생자들은 미노타우로스에게 잡아 먹힐 운명이었다. 세 번째로 공물을 바칠 때가 되자 아테네의 테세우스(Theseus)가 희생될 젊은이의 한 사람으로 자원했다. 테세우스가 크레타섬에 도착했을 때 미노스 왕의 딸 아리아드네(Ariadne)가 그에게 반해 그를 돕기 위해 실뭉치를 주었다. 테세우스는 미궁에 들어가 미노타우로스를 발견하고 죽인 후 실을 사용하여 출구를 찾아냈다.

미로 탐색이 흥미로운 것은 고대 신화에 나와서거나 아름답게 꾸며진 공원에서의 즐거운 놀이라서가 아니다. 미로 탐색은 특정 경로로 이어진 공간을 탐색하는 상황과 별반 다르지 않다. 도로망은 확실히 그 한 예가 되지만, 더 추상적인 것을 탐구하고자 하면 문제는 더욱더 흥미로워진다. 서로 연결된 컴퓨터 네트워크에서 한 컴퓨터가 또 다른 컴퓨터에 연결되어 있는지 확인하고 싶고, 사람들이 서로 연결된 소셜 네트워크에서 임의의 한 사람이 다른 사람과 연결되는지를 알고 싶을 수도 있다.