[Algorithm] DFS (깊이 우선 탐색)

1. DFS : Depth-First Search

 깊이 우선 탐색이라고 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. DFS는 스택 자료 구조, 재귀 함수를 이용한다. 구체적인 동작 과정은 다음과 같다.

---

•  탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
•  스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
•  더 이상 2번 과정을 수행할 수 없을 때까지 반복한다.

---

 과정을 그림으로 나타내면 다음과 같다.

이러한 과정을 반복하였을 때, 전체 노드의 탐색 순서(스택에 들어간 순서)는 다음과 같다.

python 코드로 구현하면 다음과 같다.