Tree
- 부모-자식 관계의 계층이 존재하는 자료구조
- 배열로 구현한다.
깊이 우선 탐색 : DFS(Depth-First Search)
- Bianry tree를 순회할 때 사용하는 in-order, pre-order, post-order 순회 방법
- 시작점에서 해당 자식노드를 방문하였으면 그 자식노드의 자식노드...를 끝까지 파고들어 마지막 노드가 나올 때까지 탐색한 후 다시 가장 가까운 형제 노드를 탐색한다. 이때 자식 노드에서 다시 가까운 정점으로 돌아오는 과정을 백트래킹이라고 한다.
- DFS는 현재 탐색하고 있는 경로 상의 노드들만 기억하면 되기 때문에 BFS에 비해 저장공간의 수요가 비교적 적다.
- DEF는 재귀로 구현하면 코드가 깔끔해진다.
- stack을 이용해서 탐색 (마지막에 쌓인 애부터 실행)
너비 우선 탐색 :BFS(Breath-First Search)
- 탐색을 하는 순서에 있어 너비(층)이 우선시된다.
- 시작점에서 자식노드를 모두 방문한 뒤에 자식노드의 자식노드들을 모두 방문하고... 이런식으로 자식 계층을 모두 방문한 후 다음 자식노드로 넘어간다.
- queue를 이용해서 탐색(먼저 들어온 애부터 실행 FIFO)
- 두 노드사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용한다.
참고
- Graph Data Structures in JavaScript for Beginners
- https://smlee729.github.io/python/network%20analysis/2015/04/09/1-networkx-dfs-bfs.html
- https://jun-choi-4928.medium.com/javascript%EB%A1%9C-%ED%8A%B8%EB%A6%AC-bfs-dfs-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0-e96bcdadd1f3
- [자료구조 알고리즘] Graph 검색 DFS, BFS 구현 in Java
