Breadth First Search(BFS)는 그래프 탐색 방식중 하나이다. BFS는 시작 정점을 기준으로 가까운 정점부터 차례대로 방문하는 방식이다. 이런 특성을 통하여 가중치가 없는 간선 그래프에서 가장 가까운 경로를 발견할때 사용할 수 있다.
구현
시작 정점 v에서 출발하고, 큐 Q에 시작 정점을 추가하고 VISITED 상태로 만든 후 다음 과정을 반복한다.
1. Q가 비었다면 종료한다. 정점이 있다면 해당 정점 v에 대하여 다음을 실행한다
2. v에 인접한 정점중 UNVISITED인 정점을 큐에 삽입하고, VISITED상태로 변경한다.
용어
unvisited vertex: 아직 방문하지 않은 정점
visited vertex: 방문한 정점
unexlored edge: 아직 방문하지 않은 간선
discovery edge: 방문한 간선으로, 해당 간선으로 진행하여 새로운 정점을 찾은 경우.
cross edge: 방문한 간선으로, 해당 간선으로 진행하였지만, 이미 방문한 정점이였던 경우. 이때 BFS의 특성에 따라서 cross edge는 같거나 1 낮은 level을 가지는 정점으로만 연결된다.
효율
정점과 간선에 접근하고, VISITED인지 확인하거나 VISITED로 라벨을 변경하는것에 O(1) 시간이 소요된다.
즉, n개의 정점과 m개의 간선을 가진 그래프에서 BFS는 O(n + m)의 시간 복잡도를 가진다.
응용
최적 경로찾기
'CS > 자료구조 (Data Structure)' 카테고리의 다른 글
[자료구조] 16. 방향 그래프(Directed Graph = Digraph) (0) | 2023.08.16 |
---|---|
[자료구조] 14. DFS (0) | 2023.08.08 |
[자료구조] 13. 그래프(Graph) (0) | 2023.08.02 |
[자료구조] 12. 해시 테이블(Hash table) (0) | 2023.07.31 |
[자료구조] 12. AVL 트리(AVL Tree) (0) | 2023.07.28 |