-
BFS (Breadth First Search) : 너비 우선 탐색Computer Science/자료구조&알고리즘 2021. 2. 15. 23:12
BFS, 너비 우선 탐색이란,
그래프 상에 존재하는 정점을 방문할 때마다 그 다음으로 주변의 인접한 정점들을 우선적으로 탐색해나가는 탐색 방법을 말한다.
반복문과 큐를 이용하여 구현할 수 있다.
수도코드
bfs(int i){
queue q;
q.push(i);
visited[i] = true;
while(!q.empty()){
int v = q.pop();
for(i in adjacent vertices of v){
if(!visited[i]){
q.push(i);
visited[i] = true;
}
}
}
}
노드를 방문할 때마다 방문하지 않은 주변 노드들이 큐에 들어간다. 큐에 한번 들어가는 순간 방문이 예정되어 있으므로 방문 표시를 한다. (그래야 중복 방문이 제대로 방지된다.) 큐에 들어간 순서대로 즉, 먼저 방문한 노드의 인접 노드를 우선적으로 방문하게 된다.
시간 복잡도 : 정점의 개수를 |V|, 간선의 개수를 |E|라고 할 때(무향 그래프일 경우에는 간선 하나당 방향이 서로 다른 유향 간선 2개로 친다), 정점의 방문 횟수와 간선 탐색 수를 primary operation이라고 가정하면 최악의 경우 O(|V| + |E|)
'Computer Science > 자료구조&알고리즘' 카테고리의 다른 글
합병 정렬 (Merge Sort) 알고리즘 (0) 2021.02.17 힙(heap)의 삽입과 삭제 (0) 2021.02.16 DFS (Depth First Search) : 깊이 우선 탐색 (0) 2021.02.15 그래프 (0) 2021.02.13 자료구조 기초 정리 (시간 복잡도, 추상 데이터 타입, 선형 자료구조, 트리) (0) 2021.02.13