[개념] BFS(Breadth-First Search) - python

BFS(Breadth Fisrt Search)은 너비 우선 탐색이라는 뜻으로, 하나의 정점으로부터 가까운 노드부터 탐색하는 알고리즘이다. BFS는 그래프 탐색의 일종이다.

 

그래프 탐색?

- 하나의 정점으로부터 시작하여 모든 정점을 한번씩 방문하는 것

 

직관적인 이해를 위해 먼저 트리를 대상으로 살펴보겠다. 

BFS는 너비 우선 탐색이라는 이름에 맞게 가로 노드들을 순서대로 방문한다.

1번 행을 모두 탐색하면 2번 행, 2번 행을 모두 탐색하면 3번행... 순서로 탐색을 이어나간다. 

 

 

BFS 순서

탐색 순서: A - B - C - D - E - F

 

 

이제는 무향 그래프에서 수행하는 BFS를 살펴보겠다. 

 

시작

해당 정점을 기준으로 탐색을 시작한다.

 

 

Level 2

첫 번째로 방문한 노드와 인접한 노드들을 방문한다.

 

 

Level 3

두 번째로 방문한 노드와 인접한 노드가 없으므로, 세 번째로 방문한 노드와 네 번째로 방문한 노드의 인접한 노드만 방문한다.

 

 

Level 4

여섯 번째로 방문한 노드와 인접한 노드를 마지막으로 여덟 번째 방문 노드에서는 더 이상 탐색할 곳이 없기 때문에 탐색을 종료한다.

 

 

위 간선들 중 노드 방문에 이용한 간선들만 남기면 아래 그림과 같이 트리가 된다.

 

너비 우선 트리

해당 트리를 '너비 우선 트리'라 한다.

 

 

 

이제 BFS 알고리즘을 큐를 이용해 구현해보겠다.

def BFS(graph, start):
	visited = []	# 방문 표시를 할 리스트
	queue = []
    
	# 큐에 시작 노드 넣기
 	queue.append(start)
 
 	# 큐가 차있는 동안
  	while queue:
    	# 큐에 가장 앞에 있는 요소 꺼내오기
  		node = queue.pop(0)
        # 방문 리스트에 노드가 없다면
 		if node not in visited:
			visited.append(node)
 			queue.extend(graph[node])
 
 	return visited

 graph = {
        '1': ['2','3','4'],
        '2': ['1','3'],
        '3': ['1','2','4','5'],
        '4': ['1','3','6','7'],
        '5': ['3'],
        '6': ['4','7','8'],
        '7': ['4','6','8'],
        '8': ['6','7']
    }

 

 

참고 - 문병로, '쉽게 배우는 알고리즘', 한빛 아카데미