그래프나 트리를 출발점에서 가까운 순서(간선 1개로 갈 수 있는 정점, 다음으로 2개로 갈 수 있는 정점…)로 방문하는 탐색 방법. 큐를 사용하여 구현하며, 간선에 가중치가 없는 그래프에서는 출발점에서 각 정점까지의 최소 간선 수가 구해진다. 영어 머리글자로 BFS라고도 한다.
일본어 명칭: 幅優先探索
너비 우선 탐색(Breadth-First Search)은(는) 자료 구조와 알고리즘 등 1개 분야의 연습 문제 4개에 나와요.
분야: 자료 구조와 알고리즘
정답: B. 인접 리스트. 기억 영역은 정점 수와 간선 수의 합에 비례하며, 어떤 정점에서 나가는 간선을 차례로 따라가는 데 적합하다
인접 행렬은 정점 수 V에 대해 V×V의 표를 사용하므로, 100만 정점에서는 10¹²개의 원소가 필요하며 원소 하나를 1비트로 해도 약 125 GB가 됩니다. 인접 리스트는 각 정점에 이어진 정점만 나열하므로 기억 영역은 O(V + E)이며, 이 예라면 수백만 건 정도로 충분합니다. 인접 행렬은 간선의 유무를 O(1)로 조사할 수 있는 이점이 있어, 간선이 많은(밀집한) 그래프나 정점이 적은 그래프에 적합합니다. 너비 우선 탐색이나 다익스트라 알고리즘처럼 정점에서 나가는 간선을 차례로 따라가는 처리에서는 인접 리스트가 더 효율적으로 동작합니다.
큐는 프린터의 인쇄 대기, 태스크 간에 데이터를 주고받는 메시지 큐, 너비 우선 탐색 등에 쓰입니다.
빈 큐에 A, B, C의 순서로 원소를 넣고 하나를 꺼낸 뒤, D를 넣고 하나를 꺼내고, E를 넣고 하나를…너비 우선 탐색이나 다익스트라 알고리즘처럼 정점에서 나가는 간선을 차례로 따라가는 처리에서는 인접 리스트가 더 효율적으로 동작합니다.
정점이 100만 개, 간선이 300만 개 정도인 도로망처럼 정점 수에 비해 간선이 적은(희소한) 그래프를 …너비 우선 탐색은 출발점에서 간선 1개로 갈 수 있는 정점, 2개로 갈 수 있는 정점…처럼 가까운 순서로 방문합니다.
간선에 가중치가 없는 그래프에서, 출발점에서 각 정점까지의 최소 간선 수를 구하고 싶다. 적합한 탐색 방법…A, B, C, D, E, F는 출발점에서 가까운 순서로 방문하는 너비 우선 탐색의 순서입니다.
간선에 방향이 없는 그래프에서 각 정점의 이웃 정점이 다음과 같다. A: B, C / B: A, D, E …스택(Stack) 깊이 우선 탐색(Depth-First Search) 재귀(Recursion) 다익스트라 알고리즘(Dijkstra's Algorithm) 동적 계획법(Dynamic Programming) 시간 복잡도(Time Complexity) 안정 정렬(Stable Sort) 연결 리스트(Linked List) 이진 탐색 트리(Binary Search Tree) 이진 탐색(Binary Search)