너비 우선 탐색

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

너비 우선 탐색(BFS)은 그래프를 탐색하는 알고리즘으로, 시작 노드에서 인접한 모든 노드를 먼저 방문하며, 큐(Queue) 자료구조를 사용하여 구현된다. BFS는 최단 경로를 찾는 데 유용하며, 그래프의 모든 정점과 간선을 탐색하는 시간 복잡도 O(|V|+|E|)를 가진다. 이 알고리즘은 완전하며, 그래프가 유한하고 해가 존재하면 반드시 해를 찾는다. BFS는 가비지 수집, 최단 경로 탐색, 최대 흐름 계산 등 다양한 분야에 응용되며, 특히 이산가족 상봉 경로 최적화, DMZ 평화적 활용 방안 연구, 재난 대응 시스템 구축, 교통 체증 완화 등 한국의 특수한 상황과 사회 문제 해결에도 활용될 수 있다.

더 읽어볼만한 페이지

검색 알고리즘 - 유전 알고리즘
유전 알고리즘은 생물 진화 과정을 모방하여 최적해를 탐색하는 계산 최적화 기법으로, 해를 유전자로 표현하고 적합도 함수를 통해 평가하며 선택, 교차, 돌연변이 연산을 반복하여 최적해에 근접하는 해를 생성하며, 성능은 매개변수에 영향을 받고 초기 수렴 문제 해결을 위한 다양한 변형 기법과 관련 기법이 존재한다.
검색 알고리즘 - 역색인
역색인은 단어와 해당 단어가 포함된 문서 간의 관계를 나타내는 자료 구조이며, 검색 엔진의 쿼리 속도를 최적화하는 데 사용된다.
그래프 알고리즘 - 페이지랭크
페이지랭크는 래리 페이지와 세르게이 브린이 개발한 알고리즘으로, 하이퍼링크로 연결된 문서 집합에서 웹 페이지의 상대적 중요도를 측정하며, 링크를 투표로 간주하여 페이지 순위를 재귀적으로 결정하고, 구글 검색 엔진의 초기 핵심 알고리즘으로 활용되었으며, 다양한 분야에서 활용된다.
그래프 알고리즘 - 깊이 우선 탐색
깊이 우선 탐색(DFS)은 그래프 탐색 알고리즘으로, 시작 정점에서 깊이를 우선하여 탐색하고 목표 노드를 찾거나 더 이상 진행할 수 없을 때 백트래킹을 통해 다른 경로를 탐색하며, 재귀나 스택으로 구현되어 미로 찾기, 위상 정렬, 연결 요소 찾기 등에 활용된다.

너비 우선 탐색
알고리즘 개요
종류	검색 알고리즘
자료 구조	그래프
시간 복잡도	O(\|V\|+\|E\|) = O(b^d)
공간 복잡도	O(\|V\|) = O(b^d)
최적성	예 (비가중 그래프의 경우)
완전성	예
탐색 방식
노드가 확장되는 순서

2. 알고리즘

너비 우선 탐색(BFS)은 큐 자료 구조를 사용하여 구현하는 것이 일반적이다. 깊이 우선 탐색의 비재귀적 구현과 유사하지만, 다음과 같은 두 가지 주요 차이점이 있다.

1. 스택(후입선출) 대신 큐(선입선출)를 사용한다.

2. 정점을 큐에 넣기 전에 해당 정점이 탐색되었는지 확인한다.

만약 그래프가 트리라면, 큐를 스택으로 바꾸어 깊이 우선 탐색 알고리즘을 얻을 수 있다. 일반적인 그래프에서도 스택을 큐로 바꾸어 너비 우선 탐색을 구현할 수 있지만, 표준적인 방식은 아니다.^[10]

BFS에서 '노드'와 '정점'은 서로 바꿔 사용할 수 있는 용어이다. 각 노드의 '부모' 속성은 BFS가 실행된 후, 목적지 노드에서 시작 노드까지 역추적하여 최단 경로를 찾는 데 사용된다. 노드의 탐색 여부는 집합(set)이나 노드의 속성을 통해 구현할 수 있다.

2. 1. 동작 방식

이 알고리즘은 깊이 우선 탐색의 비재귀적 구현과 유사하지만, 두 가지 면에서 다르다.

# 스택(후입선출) 대신 큐(선입선출)를 사용한다.

# 정점을 큐에 넣기 전에 해당 정점이 탐색되었는지 확인한다. 스택에서는 정점을 꺼낼 때까지 이 확인을 늦춘다.^[10]

만약 그래프가 트리라면, 이 너비 우선 탐색 알고리즘의 큐를 스택으로 바꾸면 깊이 우선 탐색 알고리즘이 된다. 일반적인 그래프의 경우, 반복적인 깊이 우선 탐색 구현의 스택을 큐로 바꾸는 것도 너비 우선 탐색 알고리즘을 생성하지만, 다소 표준적이지 않은 방식이다.^[10]

큐 ''Q''는 알고리즘이 현재 탐색하고 있는 경계선을 포함한다.

노드는 집합에 저장하거나 각 노드의 속성을 통해 탐색된 것으로 표시할 수 있으며, 이는 구현에 따라 달라진다.

''노드''는 일반적으로 ''정점''과 상호 교환하여 사용할 수 있다.

각 노드의 ''부모'' 속성은 BFS가 실행되고 선행 노드가 설정된 후, 목적지 노드에서 시작 노드까지 역추적하여 최단 경로의 노드에 접근하는 데 유용하다.

너비 우선 탐색은 ''너비 우선 트리''를 생성한다.

너비 우선 탐색의 동작 방식은 다음과 같다.

# 루트 노드를 빈 큐에 추가한다.

# 큐의 맨 앞에서 노드를 꺼내 다음 처리를 한다.

## 노드가 탐색 대상이면 탐색을 중단하고 결과를 반환한다.

## 그렇지 않으면 노드의 자식 중 미탐색 노드를 모두 큐에 추가한다.

# 만약 큐가 비어 있다면, 그래프 내의 모든 노드에 대해 처리가 완료되었으므로 탐색을 중단하고 "찾을 수 없음"을 반환한다.

# 2로 돌아간다.

노드의 전개로 얻어지는 자식 노드는 큐에 추가된다. 방문 여부 관리는 배열이나 집합 등으로도 할 수 있다.

2. 2. 의사 코드 (Pseudocode)

다음은 너비 우선 탐색 알고리즘의 일반적인 의사 코드이다.

'''입력''': 그래프 와 의 시작 정점

'''출력''': 목표 상태. ''부모'' 링크는 로 돌아가는 최단 경로를 추적한다.^[9]

```

1 '''절차''' BFS(G, root) '''는'''

2 Q를 큐로 정의한다

3 root를 탐색됨으로 표시한다

4 Q.enqueue(root)

5 '''while''' Q가 비어 있지 않다면 '''do'''

6 v := Q.dequeue()

7 '''if''' v가 목표라면 '''then'''

8 '''return''' v

9 '''for all''' v에서 w로 가는 간선 '''in''' G.adjacentEdges(v) '''do'''

10 '''if''' w가 탐색됨으로 표시되지 않았다면 '''then'''

11 w를 탐색됨으로 표시한다

12 w.parent := v

13 Q.enqueue(w)

```

위 코드는 다음과 같이 동작한다.

1. 루트 노드를 빈 큐에 추가한다.

2. 노드를 큐의 맨 앞에서 꺼내 다음 처리를 한다.

노드가 탐색 대상이면 탐색을 중단하고 결과를 반환한다.
그렇지 않으면 노드의 자식 중 미탐색 노드를 모두 큐에 추가한다.

3. 만약 큐가 비어 있다면, 그래프 내의 모든 노드에 대해 처리가 완료되었으므로 탐색을 중단하고 "찾을 수 없음"을 반환한다.

4. 2로 돌아간다.

노드의 전개로 얻어지는 자식 노드는 큐에 추가된다. 방문 여부 관리는 배열이나 집합 등으로도 할 수 있다.

다음은 v를 정점으로 하는 너비 우선 탐색 함수의 의사 코드이다.

```

'''function''' 너비 우선 탐색(v)

Q ← 빈 큐

v에 방문 표시를 한다

v를 Q에 추가한다

'''while''' Q가 비어 있지 않다 '''do'''

v ← Q에서 꺼낸다

v를 처리한다

'''for each''' v에 연결된 정점 i '''do'''

'''if''' i가 미방문 '''then'''

i에 방문 표시를 한다

i를 Q에 추가한다

2. 3. 구현 (Python)

python

def breadth_first_search(problem):

# FIFO 방식의 open_set

open_set = Queue()

# 방문한 노드를 저장하는 빈 집합

closed_set = set()

# 메타 정보를 저장하는 딕셔너리 (경로 구성을 위해 사용)

meta = dict() # 키 -> (부모 상태, 자식 노드에 도달하기 위한 행동)

# 초기화

start = problem.get_start_state()

meta[start] = (None, None)

open_set.enqueue(start)

while not open_set.is_empty():

parent_state = open_set.dequeue()

if problem.is_goal(parent_state):

return construct_path(parent_state, meta)

for (child_state, action) in problem.get_successors(parent_state):

if child_state in closed_set:

continue

if child_state not in open_set:

meta[child_state] = (parent_state, action)

open_set.enqueue(child_state)

closed_set.add(parent_state)

def construct_path(state, meta):

action_list = list()

while True:

row = meta[state]

if len(row) == 2:

state = row[0]

action = row[1]

action_list.append(action)

else:

break

return action_list.reverse()

```

다음은 파이썬을 이용한 너비 우선 탐색 알고리즘의 구현 예시이다.^[1]

다음은 너비 우선 탐색의 처리 과정이다.

루트 노드를 빈 큐에 추가한다.
노드를 큐의 맨 앞에서 꺼내 다음 처리를 한다.
노드가 탐색 대상이면 탐색을 중단하고 결과를 반환한다.
그렇지 않으면 노드의 자식 중 미탐색 노드를 모두 큐에 추가한다.
만약 큐가 비어 있다면, 그래프 내의 모든 노드에 대해 처리가 완료되었으므로 탐색을 중단하고 "찾을 수 없음"을 반환한다.
2로 돌아간다.

노드의 전개로 얻어지는 자식 노드는 큐에 추가된다. 방문 여부 관리는 배열이나 집합 등으로도 할 수 있다.^[2]

```python

import networkx as nx

import collections

# 그래프 G의 너비 우선 탐색 트리 T를 반환하는 함수

def bfs(G):

V = [v for v in G.nodes()]

Q = collections.deque([V[0]])

explored = {v: False for v in G.nodes()}

explored[V[0]] = True

T_edges = [] # T에 포함된 변에 해당하는 튜플을 기록하는 목록

while len(Q) != 0:

v = Q.popleft()

unexplored_neighbors = [i for i in G.neighbors(v) if not explored[i]]

for i in unexplored_neighbors:

Q.append(i)

T_edges += [(v, i)] # i에 처음 도달한 경우에만 변을 목록에 추가

explored[i] = True

return G.edge_subgraph(T_edges).copy() # G의 부분 그래프로 T를 반환

```^[3]

3. 분석

너비 우선 탐색은 완전한(complete) 알고리즘이다. 즉, 인접 리스트, 인접 행렬 등으로 표현되는 유한 그래프에서 해가 존재한다면 반드시 해를 찾는다.^[13] 일반적으로 너비 우선 탐색은 시작 노드와 종료 노드 간의 최단 경로를 반환한다.

만약 그래프가 가중치를 가진다면, 첫 번째 노드의 인접 노드가 최적의 목표 노드라고 단정할 수 없지만, 이 문제는 간선의 비용을 고려하는 균일 비용 탐색으로 해결할 수 있다.

3. 1. 시간 복잡도

너비 우선 탐색의 시간 복잡도는 최악의 경우 모든 정점과 모든 간선을 탐색하므로 O(|V|+|E|)로 표현할 수 있다. 여기서 |V|는 정점의 수이고, |E|는 그래프의 간선 수이다.^[11] O(|E|)는 입력 그래프의 희소성에 따라 O(1)에서 O(|V|²)까지 다양할 수 있다.^[11]

최악의 경우, 너비 우선 탐색은 모든 경로를 고려해야 하므로, 너비 우선 탐색의 시간 복잡도는 O(|E|)이다. 여기서 |E|는 그래프 내의 간선 수이다.

3. 2. 공간 복잡도

그래프의 정점 수를 미리 알고 있으며, 큐에 이미 추가된 정점을 확인하기 위해 추가적인 자료 구조를 사용하는 경우, 공간 복잡도는

O(|V|)

로 표현할 수 있다. 여기서

|V|

는 정점의 수이다. 이는 알고리즘 구현에 사용되는 그래프 표현에 따라 달라질 수 있는 그래프 자체에 필요한 공간 외에 추가적인 공간이다.

너비 우선 탐색은 발견된 모든 노드를 기록해야 하므로 공간 복잡도는 O(|V|)가 된다. 여기서 |V|는 그래프 내 노드의 수이다. 또는 분기의 최대 수를 B, 트리의 최장 경로의 길이를 M이라고 할 때,

O(B ^ M)

으로 표현할 수도 있다. 이는 지수 함수이기 때문에 너비 우선 탐색은 방대한 정보에서 탐색하는 데 적합하지 않은 근거가 된다.

3. 3. 완전성 (Completeness)

너비 우선 탐색은 완전한(complete) 알고리즘이다. 즉, 인접 리스트, 인접 행렬 등으로 표현되는 유한 그래프에서 해가 존재한다면 반드시 해를 찾는다.^[13] 인공 지능 분야에서 그래프 탐색 방법을 적용할 때 입력이 무한 그래프의 암시적 표현일 수 있는데, 이러한 맥락에서 탐색 방법은 목표 상태가 존재할 경우 이를 찾도록 보장되면 완전하다고 설명된다.^[13] 너비 우선 탐색은 완전하지만, 깊이 우선 탐색은 그렇지 않다.^[13] 암시적으로 표현된 무한 그래프에 적용될 때 너비 우선 탐색은 결국 목표 상태를 찾지만, 깊이 우선 탐색은 목표 상태가 없는 그래프의 일부에서 길을 잃고 절대 돌아오지 못할 수 있다.^[13]

3. 4. 최적성 (Optimality)

일반적으로 너비 우선 탐색은 최적이며, 항상 시작 노드와 종료 노드 간의 최단 경로를 반환한다. 만약 그래프가 가중치를 가진다면, 첫 번째 노드의 인접 노드가 최적의 목표 노드라고 단정할 수 없지만, 이 문제는 엣지(edge)의 비용을 고려하는 균일 비용 탐색으로 해결할 수 있다.

4. 장단점

너비 우선 탐색(BFS)은 출발 노드에서 목표 노드까지의 최단 경로를 보장한다는 장점이 있다. 하지만 경로가 매우 길 경우 탐색 가지가 급격히 증가하여 많은 기억 공간을 필요로 한다는 단점이 있다. 또한 해가 존재하지 않을 때, 유한 그래프의 경우에는 모든 그래프를 탐색한 후에 실패로 끝나며, 무한 그래프의 경우에는 결코 해를 찾지도 못하고 탐색이 끝나지 않는다.^[10]

4. 1. 장점

출발 노드에서 목표 노드까지의 최단 길이 경로를 보장한다.^[10]

4. 2. 단점

경로가 매우 길 경우, 탐색 가지가 급격히 증가함에 따라 더 많은 기억 공간을 필요로 한다.
해가 존재하지 않는다면, 유한 그래프(finite graph)의 경우에는 모든 그래프를 탐색한 후에 실패로 끝난다.
무한 그래프(infinite graph)의 경우에는 결코 해를 찾지도 못하고, 끝내지도 못한다.^[10]

5. 응용

너비 우선 탐색(BFS)은 다양한 분야에서 활용된다. 특히 그래프 이론에서 많은 문제를 해결하는 데 사용될 수 있다.^[14]

5. 1. 그래프 이론

너비 우선 탐색은 다음과 같은 많은 그래프 이론 문제를 해결하는 데 사용될 수 있다.

가비지 수집, 체니의 알고리즘 복사
두 노드 ''u''와 ''v'' 사이의 최단 경로 찾기 (경로 길이는 간선 수로 측정) (깊이 우선 탐색에 비해 장점)^[14]
(역) 커틸-매키 메쉬 넘버링
포드-풀커슨 방법을 이용한 흐름 네트워크에서 최대 흐름 계산
이진 트리의 직렬화/역직렬화 (정렬된 순서로의 직렬화와 비교)를 통해 트리를 효율적인 방식으로 재구성할 수 있다.
아호-코라식 패턴 매처의 ''실패 함수'' 구성
그래프의 이분성 테스트
그래프의 추이적 폐쇄를 계산하기 위한 병렬 알고리즘 구현^[15]

폭넓이 우선 탐색은 그래프 이론에서 많은 문제를 해결하는 데 사용할 수 있다. 다음은 그 예시이다.

그래프 내 모든 연결 요소를 찾는다. 폭넓이 우선 탐색으로 도달할 수 있는 노드의 집합은 초기 노드를 포함하는 최대 연결 요소이다.
하나의 연결 요소 내 모든 노드를 찾는다.
가중치가 없는 그래프의 최소 신장 트리를 구한다.
가중치가 없는 그래프의 단일 시작점 최단 경로 문제를 해결한다.
그래프가 이분 그래프인지 테스트한다. 만약 폭넓이 우선 탐색의 같은 단계의 노드 집합에 존재하는 노드에 합류하는 변이 있다면, 그래프에는 홀수 길이의 사이클이 존재하고 이분 그래프가 아니다.

5. 2. 기타

너비 우선 탐색은 다음과 같은 많은 그래프 이론 문제를 해결하는 데 사용될 수 있다.

가비지 수집, 체니의 알고리즘 복사^[14]
두 노드 ''u''와 ''v'' 사이의 최단 경로 찾기 (경로 길이는 간선 수로 측정) (깊이 우선 탐색에 비해 장점)^[14]
(역) 커틸-매키 메쉬 넘버링
포드-풀커슨 방법을 이용한 흐름 네트워크에서 최대 흐름 계산
이진 트리의 직렬화/역직렬화 (정렬된 순서로의 직렬화와 비교)를 통해 트리를 효율적인 방식으로 재구성
아호-코라식 패턴 매처의 ''실패 함수'' 구성
그래프의 이분성 테스트
그래프의 추이적 폐쇄를 계산하기 위한 병렬 알고리즘 구현^[15]
그래프 내 모든 연결 요소 찾기
하나의 연결 요소 내 모든 노드 찾기
가중치가 없는 그래프의 최소 신장 트리 구하기
가중치가 없는 그래프의 단일 시작점 최단 경로 문제 해결

6. 한국의 특수한 상황

너비 우선 탐색(BFS)은 남북 관계, 사회 문제 해결 등 한국의 특수한 상황에서 다양한 문제 해결에 응용될 수 있다.

6. 1. 남북 관계

너비 우선 탐색(BFS)은 그래프 이론을 활용하여 다음과 같은 남북 관계 문제를 해결하는 데 응용할 수 있다.

이산가족 상봉 경로 최적화: 이산가족 상봉 시 최적의 이동 경로를 탐색하는 데 BFS 알고리즘을 응용할 수 있다.
DMZ 평화적 활용 방안 연구: DMZ를 평화적으로 활용하기 위한 최적의 경로 및 시설 배치 등을 연구하는 데 BFS 알고리즘이 도움이 될 수 있다.

6. 2. 사회 문제 해결

너비 우선 탐색(BFS)은 다음과 같은 사회 문제 해결에 활용될 수 있다.

재난 대응 시스템 구축: 재난 발생 시 최적의 대피 경로 및 구호 물품 전달 경로를 탐색하는 데 BFS 알고리즘을 활용할 수 있다.
교통 체증 완화: 도시 내 교통 체증을 완화하기 위한 최적의 신호 체계 및 도로망 설계를 연구하는 데 BFS 알고리즘이 활용될 수 있다.

참조

_[1] 문서 that is, a node satisfying the specified property
_[2] 서적 Introduction to Algorithms MIT Press 2009
_[3] 논문 Depth-First Iterative Deepening: An Optimal Admissible Tree Search https://doi.org/10.7[...] 1985
_[4] 웹사이트 Graph500 benchmark specification (supercomputer performance evaluation) http://www.graph500.[...] Graph500.org, 2010 2015-03-15
_[5] 간행물 Der Plankalkül http://zuse.zib.de/i[...] Konrad Zuse Internet Archive
_[6] 컨퍼런스 Proceedings of the International Symposium on the Theory of Switching Harvard University Press
_[7] 서적 The Algorithm Design Manual Springer
_[8] 논문 An Algorithm for Path Connections and Its Applications
_[9] 웹사이트 Introduction to algorithms http://worldcat.org/[...]
_[10] 웹사이트 Stack-based graph traversal ≠ depth first search https://11011110.git[...] 2020-06-10
_[11] 문서 Introduction to Algorithms
_[12] 문서 Cite AIMA
_[13] 문서 Artificial intelligence illuminated Jones & Bartlett Learning 2004
_[14] 서적 Algorithms for Interviews Algorithmsforinterviews.com 2010
_[15] 서적 Theoretically Efficient Parallel Graph Algorithms Can Be Fast and Scalable 2019-08-21

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com