DFS(Depth-First Search)와 BFS(Breadth-First Search) 모두 대표적인 그래프에서 모든 정점을 방문하기 위한 탐색법이다.
그래프란?
그래프는 정점과 간선을 통해 자료를 표현하는 방식이다.
정점(Vertex)은 대상 및 개체를 나타낸다.
간선(Edge)은 정점간의 관계를 나타낸다.
간선은 방향성을 가질 수 있으며, 가중치를 가질 수도 있다.
BFS, 너비우선 탐색
직관적인 이해를 위해 트리에서의 너비 우선 탐색 예시를 가져왔다.
루트를 기준으로 먼저 깊이가 1인 루트의 자식을 차례로 방문한다.
그 다음 깊이가 2인 루트의 자식의 자식을 방문한다.
위 방식으로 깊이를 늘려가며 모든 노드를 탐색하는 방식이다.
즉 루트에서 시작하여 인접한 노트를 먼저 탐색하는 방식이다.
위와같은 이유로 너비 우선 탐색(Breadth-First Search)라고 불린다.
BFS의 특징
- 재귀적으로 동작하지 않는다.
- 방문한 노드를 기록해야한다. 그렇지 않으면 무한루프에 빠질 수 있다.
- 큐(Queue)를 사용하여 탐색한다.(선입선출)
- 깊이 우선 탐색보다 구현이 복잡하다.
BFS의 탐색 과정
출처 : https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html
BFS의 구현
- 자료구조 큐(Queue)를 이용하여 구현
PS에서의 BFS
- 최단경로 탐색
- 거리 탐색 등
참고자료
https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html
https://takeitoutamber.medium.com/binary-tree-right-side-view-bfs-87a215b6237c
Dev_Hyeseong