DFS 알고리즘은 그래프 완전 탐색 기법중 하나입니다
핵심이론
-
DFS 알고리즘은 그래프의 시작 노드에서 탐색할 한쪽 분기를 정하여
최대 깊이까지 탐색을 마친 후 다른 분기로 이동하여
다시 탐색을 수행합니다
-
재귀 함수를 이용하여 구현합니다
그렇기때문에 stack overflow 현상을 주의해야합니다
-
한 번 방문한 노드를 다시 방문하면 안됩니다
그래서 노드 방문 여부를 체크할 배열이 필요하고,
그래프는 인접 리스트로 표현합니다
구현
1. DFS를 시작할 노드를 정한 후 자료구조 초기화
- 원본 그래프
- 인접 리스트로 그래프 표현 (1이 시작점)
- 방문 배열
- 스택 자료구조에 시작점을 삽입
DFS를 위해 필요한 초기작업은 인접 리스트로 그래프 표현하기,
방문배열 초기화 하기,
시작 노드를 스택에 삽입하기 입니다
스택에 시작 노드를 1로 삽입할 때 해당 위치의 방문 배열을 체크하면
위 사진과 같이 T F F F F F 가 됩니다
2. 스택에서 노드를 꺼낸 후 노드의 인접 노드를 다시 스택에 삽입
- 스택에서 노드르 꺼내면서 탐색 순서에 꺼낸 노드를 기록
- 대상 노드의 인접 노드를 스택에 삽입
(탐색 순서 : 1)
- 노드를 삽입하여 방문 배열체크
이제 pop 을 수행하여 노드를 꺼냅닏나
꺼낸 노드를 탐색 순서에 기입하고 인접 리스트의 인접 노드를 스택에 삽입하며
방문 배열을 체크합니다
방문 배열은 T T T F F F 가 됩니다
3. 스택 자료구조에 값이 없을때 까지 반복하기
- 인접 리스트
노드 6은 인접 노드가 없으므로 삽입 연산 없음
노드 2의 인접 노드는 5, 6이지만, 방문 배열을 보면 6은 이미 방문했기 때문에
삽입하지 않음
탐색 순서 : 1 -> 3 -> 4 -> 6 -> 2 - > 5
이어서 스택에서 3을 꺼내며 탐색 순서에 기록하고
인접 노드 4를 스택에 삽입하며 방문 배열에 기록합니다
4를 꺼내며 탐색 순서에 기록하고 6을 삽입하며 방문 배열에 체크합니다
6을 꺼내며 탐색 순서애 기록합니다
6과 인접한 노드는 없으므로 추가 삽입은 없습니다
계속해서 스택에서 2를 꺼내며 탐색순서에 기록하고 2와 인접한 5 6을 삽입할 차례입니다
이때 6은 이미 방문 배열에 T로 체크되어 있으므로 5만 삽입합니다
이 과정을 스택이 빌 때 까지 계속 진행합니다
-
스택에 노드를 삽입할 때 배열을 체크하고,
-
스택에서 노드를 뺄 때 탐색 순서에 기록하며 인접 노드를 방문 배열과 대조
하며 살펴봅니다
