DFS 깊이 우선 탐색

 

 

Depth-first search

 

그래프 완전 탐색 기법 중 하나로

그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 탐색을 수행하는 알고리즘

 

 

실제 구현 시 재귀 함수를 사용하므로 스택 오버플로우를 유의해야한다

 

단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬

 

DFS는 한 번 방문한 노드에 다시 방문하면 안됨 -> 체크 배열이 필요하다는 점

 

DFS탐색 방식 : 후입선출 특성을 가지고 있음