728x90
루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법
시작 정점으로부터 가까운 정점을 먼저 방문
- 멀리 떨어져 있는 정점을 나중에 순회
- 깊게(deep) 탐색하기 전에 넓게(wide) 탐색
사용하는 경우
두 노드 사이의 최단 경로 혹은 임의의 경로를 찾기
특징
- 직관적이지 않음
- 재귀적으로 동작하지 않음
- 어떤 노드를 방문했었는지 여부를 반드시 검사해야 함.
- 큐(Queue)를 사용
- 방문한 노드들을 차례대로 저장한 후 꺼내는 자료구조
- 선입선출(FIFO) 원칙으로 탐색
- 일반적으로 큐를 이용해 반복적 형태로 구현
- 'Prim', 'Dijkstra' 알고리즘과 유사
시간 복잡도
- 인접 리스트로 표현된 그래프 : O(N + E)
- 인접 행렬로 표현된 그래프 : $O(N^2)$
- 희소 그래프(Spare Graph)의 경우,
- DFS와 마찬가지로 그래프 내에 적은 숫자의 간선만을 가짐
- 인접 행렬보다 인접 리스트를 사용하는 것이 유리!
🏷️ 참고한 블로그
728x90
