그래프 탐색이란
- 하나의 정점으로부터 시작하여 차례대로 모든 정점을 한 번씩 방문하는 것.
- Ex) 특정 도시에서 다른 도시로 갈 수 있는지 없는지 등
너비우선탐색
너비 우선 탐색이란
- 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법
- 시작 정점으로부터 가까운 정점을 먼저 방문하고, 멀리 떨어져있는 정점을 나중에 방문하는 순회 방법.
- 즉, 깊게(Deep) 탐색하기 전에 넓게(Wide) 탐색하는 것이다.
- 사용하는 경우: 두 노드 사이의 최단 경로 혹은 임의의 경로 를 찾고 싶을 때 이 방법을 선택한다.
- Ex) 모든 친구 관계를 그래프로 표현한 후, A와 B 사이에 존재하는 경로를 찾는 경우
- 깊이 우선 탐색: 모든 친구 관계를 다 살펴보아야 할지도 모름.
- 너비 우선 탐색: A와 가까운 관계부터 탐색
- BFS가 DFS보다 조금 더 복잡.
너비 우선 탐색(BFS)의 특징
- 재귀적으로 동작하지 않는다
- 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다.
- 이를 검사하지 않을 경우, 무한 루프에 빠질 수 있다.
- 방문 노드들을 차례로 저장한 후, 꺼낼 수 있는 자료 구조인 Queue를 사용한ㄷ.
- FIFO
- Prim과 Dijkstra 알고리즘과 유사하다.
너비 우선 탐색의 과정
- 깊이가 1인 모든 노드를 방문하고 나서, 그 다음에는 깊이가 2인 노드를, 그 다음은 3, 이런식으로 방문하다가 더 이상 방문할 곳이 없으면 탐색을 마친다.
아래 블로그를 참고하여 작성하였습니다.
https://github.com/WeareSoft/tech-interview
