DFS : Depth-First Search (깊이 우선 탐색) 이란?

[출처 : https://en.wikipedia.org/wiki/Depth-first_search]
DFS의 특징
정점 방문 시, 반드시 방문 여부(is_visited)를 검사하고, 방문 시 is_visited를 true로 표시한다.
정점 방문 여부를 검사하지 않으면 무한 루프에 빠질 수 있다.
시간 복잡도(Time complexity): 인접 리스트로 구현시 O(V + E) // 인접 행렬로 구현 시 O(V^2)
재귀 함수로 구현시, 별도의 자료구조가 필요하지 않으므로 메모리를 아낄 수 있다.
(BFS의 경우 quene를 사용해야 하므로 DFS에 비해 메모리를 더 사용할 수 밖에 없다.)
얻은 결과가 최단 경로라는 보장이 없다. (반면 BFS는 얻은 결과가 최단 경로이다.)
DFS의 진행
DFS를 시작할 노드를 정해서 매개변수로 전달한다.
전달 받은 매개변수가 현재 노드이므로, 현재 방문 중인 노드를 방문처리 해준다.
(is_visited[cur] = true)
현재 노드와 인접한 노드들을 반복문을 통해 하나씩 접근한다. 해당 노드를 다음 노드(next)로 설정한다.
다음 노드(next)를 이전에 방문했는지 확인한다.
만일 방문했다면 다시 방문할 필요가 없으므로 지나간다. ( continue 문 )
만일 아직 방문하지 않았다면 DFS를 재귀적으로 호출한다. ( DFS(next); )
2~4번을 더 이상 방문할 노드가 없을 때 까지 반복한다.