[BFS] Breadth First Search

BFS란
말 그대로 너비를 우선해서 그래프를 탐색하는 기법이다.

이 알고리즘의 핵심은 큐(queue) 자료구조를 사용하는 것이다. 큐를 사용할 때 가장 성능이 좋기 때문이다.

BFS는 노드를 방문하면서 인접한 노드 중 방문하지 않았던 노드의 정보만 반복적으로 큐에 넣어
먼저 큐에 들어있던 노드부터 방문하면 되는 것이다. BFS 알고리즘 구체적인 동작 과정은 아래와 같다.

1. 탐색 시작 노드 정보를 큐에 삽입하고 “방문 처리” 한다.
2. 큐에서 노드를 꺼내 방문하지 않은 인접 노드 정보를 모두 큐에 삽입하고 방문 처리한다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

여기서 “방문처리” 란 탐색한 노드를 재방문하지 않도록 구분하는 것이다.
즉, 큐에 한 번이라도 삽입된 노드를 다시 삽입하지 않도록 체크하는 것이다.
물론 큐를 사용하지 않아도 구현은 가능하다.

한편, 파이썬에서 큐를 list 타입을 사용해 자료를 입력할 때는 list.append(sth),
출력할 때는 list.pop(0) 와 같이 구현하는 경우가 있다.
하지만 list.pop(0) 은 시간 복잡도가 O(N) 이라 이렇게 구현하면 시간적으로 매우 비효율적인
코드가 만들어진다.
따라서 collections 라이브러리의 deque 를 사용하면 시간을 절약할 수 있다.
또한 인접 노드 중 방문하지 않았던 노드를 큐에 넣을 때는
파이썬 데이터 타입 중 set을 사용하면 아주 쉽게 구현할 수 있다.
일반적인 경우 실제 수행시간은 DFS보다 BFS가 좋은 편이다.

import collections

# BFS algorithm
def bfs(graph, root):
	visited, queue = set(), collections.deque([root])
	visited.add(root)

	while queue:
		
		# Dequeue a vertex from queue
		vertex = queue.popleft()
		print(str(vertex) + “ “, end=“”)

		# If not visited, mark it as visited, and 
		# enqueue it
		for neighbour in graph[vertex]:
			if neighbour not in visited:
				visited.add(neighbour)
				queue.append(neighbour)
				
if __name__ == ‘__main__’:
	graph = {0:[1,2], 1:[2], 2:[3], 3:[1,2]}
	print(“Following is Breath First Traversal: “)
	bfs(graph, 0)

시간 복잡도는 O(V + E)로 V는 node 개수이고, E는 edge 개수이다.