그래프 탐색 알고리즘 : BFS (Python)

BFS

---

bfs gif

 

- 개념 : 가까운 노드부터 탐색하는 너비 우선 탐색 알고리즘 (DFS는 최대한 멀리 있는 노드 우선 탐색)

- 큐 자료구조 이용 (= 파이썬 deque 라이브러리)

- 시간 복잡도 : O(N). (실제 수행 시간은 DFS보다 좋은 편이다. 이유 - DFS의 재귀함수 사용)

 

- 장점 :

  1) 현재 노드에서 가까운 곳부터 찾기 때문에 경로를 탐색 시 먼저 찾아지는 해답이 곧 최단경로임을 보장한다.

  2) 노드의 수가 적고 깊이가 얕은 해가 존재할 때 효과적이다.

 

- 단점 :

  1) 큐를 이용해서 다음에 탐색할 노드를 저장하기 때문에 더 큰 저장공간이 필요하다.

  2) 노드의 수가 늘어나면 탐색해야하는 노드 또한 많아지기 때문에 비효율적이다.

 

- 사용예 : 최단경로, 최소신장트리

 

- 구현 방식 :

  인접한 노드를 반복적으로 큐에 넣는다.

  큐 자료구조의 특성 때문에 자연스럽게 먼저 들어온 것이 먼저 나가게 되어, 가까운 노드부터 탐색을 진행하게 된다. 

 

- 구현

from collections import deque

# BFS
def bfs(graph, start, visited):
	# 큐 구현을 위해 deque 라이브러리 사용
	queue = deque([start])
	# 현재 노드를 방문 처리
	visited[start] = True

	# 큐가 빌때까지 반복
	while queue:
		v = queue.popleft()
		print(v, end=' ')
		# 해당 원소와 인접한, 아직 방문하지 않은 원소들을 큐에 삽입
		for i in graph[v]:
			if not visited[i]:
				queue.append(i)
				visited[i] = True

# 인접 리스트 : 각 노드가 연결된 정보를 리스트 자료형으로 표현
graph = [
			[], # 0번 노드와 인접한 노드
    		[2, 3, 8],
    		[1, 7],
    		[1, 4, 5],
    		[3, 5],
    		[3, 4],
    		[7],
    		[2, 6, 8],
    		[1, 7]
]

visited = [False] * 9
bfs(graph, 1, visited)

# 출력결과 : 1 2 3 8 7 4 5 6

1) 탐색 시작노드를 큐에 삽입하고 방문 처리를 한다.

2) 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.

DFS : 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 

3) 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

 

 

DFS vs BFS 선택 팁

---

 

참고 : https://loosie.tistory.com/151

1) 그래프의 모든 정점을 방문하는 것이 주요한 문제

 단순히 모든 정점을 방문하는 것이 중요한 문제의 경우 DFS, BFS 두 가지 방법 중 어느 것을 사용해도 상관 없다. 그래프가 크다면 DFS. 그래프가 크지 앟고, 검색 시작 지점으로 부터 목표 값이 멀지 않다면 BFS.

2) 각 경로의 특징을 저장해둬야 하는 문제 : DFS

 예를 들면 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용한다

3) 최단거리 구해야 하는 문제 : BFS