sm 기술 블로그
너비 우선 탐색(BFS) 본문
너비 우선 탐색(BFS) => 큐 사용
루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법.
가장 가까운 정점을 먼저 방문하고 이후 멀리 떨어져 있는 정점을 방문하는 방식이다.
특징
- 직관적이지 않다.
- 큐를 사용한다. (선입 선출이 원칙이다)
- Prim, Dijkstra 알고리즘과 유사하다.
과정
결국 이동 순서는
0 -> 1
0 -> 2
0 -> 4
1 -> 2
2 -> 3
3 -> 4
이 된다.
시간 복잡도
인접 리스트로 표현된 그래프: O(N+E)
인접 행렬로 표현된 그래프: O(N^2)
'자료구조 || 알고리즘' 카테고리의 다른 글
동적프로그래밍(Dynamic Programming) (0) | 2022.07.01 |
---|---|
백트래킹 (0) | 2022.06.28 |
깊이 우선 탐색(DFS) (0) | 2022.06.28 |
유클리드 호제법(최대공약수 구하기) (0) | 2022.06.25 |
좌표압축 (0) | 2022.06.18 |
Comments