dfs란
시작 노드에서 출발하여
탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후
다른 쪽 분기로 이동하여 탐색을 수행하는 알고리즘이다
dfs는 그래프(트리)구조로 구성되어있으며
stack을 사용하고 재귀 함수로 구현되어있다.
주의점: stackOverFlow에 주의(재귀 함수를 사용하기때문에)
dfs는 한 번 방문한 노드를 다시 방문하면 안 되므로 노드 방문 여부를
체크할 배열이 필요하다.
예를 들어보자
이런 그래프가 있다고하면
시작 노드부터 최대 깊이의 노드까지 돈다고 가정하면
스택에는 1부터 화살표방향의 노드까지의 숫자가 쌓일것이다
그러면 1->2->3->4->6 이런식으로 간다고하면
1이 스택에 쌓이고 pop()을 수행하여 다시 1을 빼고 1의 인접노드인 2와3을 스택에 저장한다
그리고 3을 pop()하고 3의 인접노드인 4를 스택에 넣는다 이런식으로 반복을하다가 스택이 비어있으면 bfs는 종료된다.
%이미 다녀간 노드는 체크 배열을 바탕으로 재삽입하면 안된다%
| 노드1 | 노드2 | 노드3 | 노드4 |
|---|---|---|---|
| 1 | 2 | 3 | 4 |
| T | T | T | T |
