728x90
반응형
깊이 우선 탐색 DFS (Depth-First Search)
그래프 완전 탐색 기법 중 하나
그래프의 시작 노드에서 출발해서 탐색할 한 쪽 분기를 정해서 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘
- 재귀 함수로 구현 -> 스택 오버플로 (stack overflow)에 유의!!
- 스택 자료 구조 이용
한번 방문한 노드를 다시 방문하면 안되므로 노드 방문 여부를 체크할 리스트 필요
그래프는 인접 리스트로 표현
탐색 방식: 후입선출 (stack 이므로!)
1. DFS 시작 시 시작 노드를 정한 후 사용할 자료 구조 초기화하기
초기작업
- 인접 리스트로 그래프 표현하기
- 방문 리스트 초기화하기
- 시작 노드 스택에 삽입하기
2. 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접노드를 다시 스택에 삽입하기
- pop 수행
- 꺼낸 노드를 탐색 순서에 기입
- 인접 리스트의 인접 노드를 스택에 삽입
- 방문 리스트 체크
3. 스택 자료 구조에 값이 없을 때까지 반복
이미 다녀간 노드는 방문 리스트를 바탕으로 재삽입하지 않는다!
그림으로 표현하면 아래와 같다!
** 노드 탐색 시 실행한 DFS의 실행 횟수 = 연결 요소 개수 **
반응형
