DFS : 깊이 우선 탐색
: 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 (깊게) 탐색하는 방법
-
특징
- 스택 자료구조 사용 (or 재귀함수)
- 모든 노드 방문하고자 할때 이 방법 선택
- 자기 자신을 호출하는 순환 알고리즘 의 형태
- 방문처리 : 어떤 노드를 방문 했었는지 여부를 반드시 검사해야 함 (무한루프 방지)
ex) 미로찾기
-
동작 순서
1)
탐색 시작 노드를 스택에 넣고 방문처리
2) 스택 최상단 노드의인접 노드중 방문하지 않는 노드를 스택에 넣고 방문처리
3) 인접 노드 모두 방문 후 스택을pop!!
4) 스택이빌 때까지 반복~~
BFS : 너비우선 탐색
: 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법
-
특징
- 큐 자료구조 사용 (선입선출(FIFO) 원칙)
- 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법 선택
- 자기 자신을 호출하는 순환 알고리즘 의 형태
- 방문처리 : 어떤 노드를 방문 했었는지 여부를 반드시 검사해야 함 (무한루프 방지)
ex) 미로찾기
-
동작 순서
1)
탐색 시작 노드를 큐에 넣고 방문처리
2) 큐에서deque(노드를 꺼내기) 하기
3) 해당 노드의인접 노드중 방문하지 않는 노드를 큐에 삽입 후 방문처리
4) 큐가빌 때까지 반복~~
< 참고 >
https://yunyoung1819.tistory.com/86
https://velog.io/@cha-suyeon/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B9%8A%EC%9D%B4-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89DFS-%EA%B3%BC-%EB%84%88%EB%B9%84-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89BFS
