파이썬 알고리즘 - DFS (Depth- First Search)

DFS (Depth- First Search)

그래프를 탐색하는 방법 중 하나인 DFS는 깊이 우선 탐색을 의미한다.

DFS는 노드에서 탐색을 시작할 때 다음 분기로 넘어가기 전 해당 분기를 끝까지 탐색하는 알고리즘으로,

스택 자료구조 혹은 재귀 함수를 이용하여 구현할 수 있다.

처음 접한다면 위처럼 간단한 말로는 이해하기 어려울 수 있기에 조금 더 구체적으로 동작 과정을 설명해보겠다.

 

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.

2. 탐색 시작 노드와 인접한 노드를 스택에 넣고 방문 처리를 한다.

3. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있다면 스택에 넣고 방문 처리를 한다.

    방문하지 않은 인접 노드가 없다면 스택에서 최상단 노드를 꺼낸다.

4. 수행할 수 없을 때까지 3번을 반복한다.

 

위 동작 과정을 적용한 예시는 다음과 같다. (1번 노드부터 시작하며 번호가 낮은 인접 노드부터 방문한다.)

 

 

파이썬에서의 DFS

[코드]

[출력결과]