1. 너비 우선 탐색 방법 (Breadth First Serach, BFS)
ㅇ 우선 가까운 인접 노드를 모두 방문한 후에, 그 다음 가까운 인접 노드를 방문하며 진행하는 방법
- 목표 정점을 탐색할 때, 시작점에 가까운 근처 정점부터 탐색하는 방법
ㅇ 특징
- 사용 자료구조
. 선입선출(FIFO)인 `큐` 자료구조를 활용하여, 반복 구조로 구현
- 가까운 노드 우선이므로, 여러 경로 존재할 경우,
. 자연스럽게 최단 경로를 일러줌
- 중간에 거치는 정점들을, 방문 리스트로써, 저장해 둘 필요 있음
. 기 방문 노드는 다시 방문 않토록, 방문한 노드를 체크할 필요 있음
ㅇ 구현 방법 : 큐를 이용한 반복 구조로 구현
- DFS(깊이우선탐색)와 달리 재귀함수로 구현 불가하여,
- 선입선출(FIFO)인 `큐` 자료구조를 활용하여, 반복 구조로 구현
ㅇ 시간복잡도 : O(V+E)
- (V : 노드 수, E : 간선 수)
ㅇ 알고리즘의 표현
- 입력 : 특정 그래프(G), 시작 정점(v)
- 출력 : 모든 도달 가능 (방문 표시한) 정점들에 대한 배열
. (방문 여부 true/false) 또는 (각각의 경로 길이)
ㅇ 용도
- 다익스트라 알고리즘 등에 쓰임
2. 알고리즘 구현 例)
ㅇ 구현 특징
- 자료구조 : 선입선출(FIFO)인 `큐` 자료구조를 활용
- 입력 : 특정 그래프(G), 시작 정점(v)
. 여기서, G는 인접 리스트에 의한 그래프 표현으로 가정 함
- 외부 데이터 : 방문한 정점들이 열거된, 크기가 |G|인, 배열 또는 리스트 (visited)
. visited[i]가, true이면 이미 방문, false 이면, 미 방문
- 출력 : 큐에서 노드를 가져올 때 마다 해당 노드 번호 출력
. 탐색되며 거치는 경로 순서대로 노드 번호가 출력됨
ㅇ 슈도 코드
BFS(G, start)
큐 Q에 정점 start(시작 노드)를 삽입
start(시작 노드)를 방문했다고 표시
while 큐가 빌 때까지 수행
큐 Q에서 정점 하나를 가져오기 (제거)
가져온 노드 출력
for 가져온 정점 주위 모든 인접 정점들에 대해 반복 수행
if 인접 정점이 미방문이면
큐 Q에 해당 인접 정점을 삽입
해당 인접 정점을 방문했다고 표시
ㅇ 파이썬 코드
def bfs(graph, start) :
queue = [start]
visited = [start]
while queue :
v = queue.pop(0)
print(v, end=' ')
for w in graph[v] :
if w not in visited :
queue.append(w)
visited.append(w)
- [참고] 사용 데이터 유형
. 그래프 표현 : 파이썬 딕셔너리(graph)
.. 형식 : graph = { 1 : [2,3,8], 2 : [1,7], ... }
. 시작 노드 : 숫자(start)
. 방문 여부 기록 : 파이썬 리스트(visited)
. 탐색 관리용 큐 : 파이썬 리스트(queue)
.. 삽입 : queue.append(), 추출 : queue.pop(0)