DFS (깊이 우선 탐색)

그래프에서 한 길을 막다른 곳까지 끝까지 따라간 뒤, 더 갈 곳이 없으면 바로 앞 갈림길로 돌아와 다른 길을 가는 방법이다. [재귀](/term/recursion)나 스택으로 구현한다. 지금 따라가는 길 위에 이미 있는 노드를 다시 만나면 사이클이 있다는 뜻이라, 두 노드가 이어져 있는지나 사이클이 있는지를 확인할 때 쓴다.