DFS(Depth First Search)
Tree나 Graph Data structure에서 루트를 탐색할 때, 하나의 branch에 들어가면 그 루트에 대해 최대한 깊게 탐색한 후 다른 branch를 탐색하기 시작한다.
앞서 배운 BFS의 구현과 상당히 유사하다. queue를 사용한 BFS와 달리 stack을 사용하게 되면 DFS의 구현이 끝난다.
그렇다면 DFS는 언제 유용하게 쓸 수 있을까?
DFS는 탐색하는 graph가 cylic한지 acyclic한지 판별할 때 유용하다. 지나간 길에 마킹을 하고 가다가 자기 자신(처음 노드)로 돌아오게 되면 그 graph는 cyclic하게 이어져있다고 판별할 수 있다.
하지만 BFS의 성질: '현재 노드로부터 추가되는 인접노드는 현재 노드랑 1만큼의 거리 차이가 있다' 라는 성질을 쓸 수 없다. 즉 거리측정이 안되고, 최단경로 또한 아니다.
아래는 BFS와 DFS의 노드 방문 순서의 차이다.
