[알고리즘] 깊이 우선 탐색 (DFS, Depth First Search)

그래프 탐색 알고리즘 중 하나이다.

그래프?

[자료구조] 그래프와 트리

[자료구조] 그래프를 코드로 나타내는 방법 (feat. C++)

깊이 우선 탐색(DFS)이란

 

루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법.

계속해서 깊게 파고 내려가는 형태를 띈다

답을 찾을 때까지 갈 수 있는 한 아래로 탐색을 반복한다.

더 이상 진행할 수 없으면, 올라와서 방문 하지 않았던 노드부터 다시 탐색을 진행한다.

깊이 우선 탐색(DFS)을 사용하는 경우

모든 노드를 방문 하고자 하는 경우에 이 방법을 선택한다.

깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단하다.

단순 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느리다.

깊이 우선 탐색(DFS)의 특징

➤ DFS는 스택 또는 재귀함수로 구현하는데, 재귀 자체가 스택 구조를 이용하는 것이므로 원리는 동일하다.

➤ 자기 자신을 호출하는 순환 알고리즘의 형태 를 가지고 있다.

➤ 전위 순회(Pre-Order Traversals)를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류이다.

➤ 구현할 때 주의할 점은, 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다는 것.

(이를 검사하지 않을 경우 무한루프에 빠질 위험이 있다.)

깊이 우선 탐색(DFS)의 과정

1. a 노드(시작 노드)를 방문한다.방문한 노드는 방문했다고 표시한다.
2. a와 인접한 노드들을 차례로 순회한다.a와 인접한 노드가 없다면 종료한다.
3. a와 이웃한 노드 b를 방문했다면, a와 인접한 또 다른 노드를 방문하기 전에 b의 이웃 노드들을 전부 방문해야 한다.
   b를 시작 정점으로 DFS를 다시 시작하여 b의 이웃 노드들을 방문한다.
4. b의 분기를 전부 완벽하게 탐색했다면 다시 a에 인접한 정점들 중에서 아직 방문이 안 된 정점을 찾는다.
   (즉, b의 분기를 전부 완벽하게 탐색한 뒤에야 a의 다른 이웃 노드를 방문할 수 있다는 뜻)
   아직 방문이 안 된 정점이 없으면 종료한다.있으면 다시 그 정점을 시작 정점으로 DFS를 시작한다.

References

https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html

https://velog.io/@hhhminme/자바스크립트로-알아보는-완전탐색

https://velog.io/@kimjihong9/깊이-우선-탐색DFS

 

 

 

 

 

 

 

TRANSLATE with x

English

Arabic	Hebrew	Polish
Bulgarian	Hindi	Portuguese
Catalan	Hmong Daw	Romanian
Chinese Simplified	Hungarian	Russian
Chinese Traditional	Indonesian	Slovak
Czech	Italian	Slovenian
Danish	Japanese	Spanish
Dutch	Klingon	Swedish
English	Korean	Thai
Estonian	Latvian	Turkish
Finnish	Lithuanian	Ukrainian
French	Malay	Urdu
German	Maltese	Vietnamese
Greek	Norwegian	Welsh
Haitian Creole	Persian

 

TRANSLATE with

COPY THE URL BELOW

Back

EMBED THE SNIPPET BELOW IN YOUR SITE

Enable collaborative features and customize widget: Bing Webmaster Portal

Back