[Graph] BFS (너비 우선 탐색)

너비 우선 탐색은 탐색 시작점의 인접한 정점들을 먼저 모두 차례로 방문한 후에, 방문했던 정점을 시작점으로 하여 다시 인접한 정점들을 차례로 방문하는 방식이다.

 

그래프를 탐색하는 방법에는 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)로 크게 2가지가 있다.

인접한 정점들에 대해 탐색을 한 후, 차례로 다시 너비 우선 탐색을 진행해야 하므로, 선입선출 형식의 자료구조인 큐를 활용한다.

BFS는 시작 정점 기준 거리가 가까운 곳부터 먼곳으로 탐색을 진행하기 때문에, 특정정점까지 가는 최단거리를 구하는데 용이하며, BFS 탐색이 종료된 경우 직전에 방문한 정점이 시점과 가장 먼 정점이라는 것을 알 수 있다.

 

개요

1. 시작정점 v를 결정하여 방문한다.
2. 정점 v에 인접한 정점 중에서
   1. 방문하지 않은 정점 w가 있다면, 정점 w를 큐에 push하고 정점 w를 방문한다. 그리고 w를 v로 하여 다시 위 순서를 반복한다.
   2. 방문하지 않은 정점이 없으면, 탐색의 방향을 바꾸기 위해서 큐에 pop(0)하여 가장 과거에 방문한 정점을 v로 하여 다시 위 순서를 반복한다
3. 큐가 공백이 될 때까지 2번을 반복한다.

 

구현

✅ 반복문1

que와 visited 에 방문할, 방문한 정점을 기록하여 모든 정점을 방문한다.

def BFS(G, v):
	# 방문체크를 위한 visited와 queue 생성
	visited = [0] * n
	queue = []

	# 시작점을 queue에 넣는다
	queue.append(v)

	# queue가 비어있지 않으면 반복
	while queue:
		# queue의 첫번째 원소 반환
		t = queue.pop(0)

		# 방문하지 않았다면
		if not visited[t]:
			# 방문 체크
			visited[t] = True
		
		# 현재 정점과 연결된 정점중 방문하지 않은 곳을 queue에 넣는다
		for i in G[t]:
			if not visited[i]:
				queue.append(i)

 

✅ 반복문2

완전그래프, 정점의 연결이 많은 경우 queue가 상당히 길어지고 메모리나 효율성이 떨어질 수 있기 때문에 아래처럼 수정하면, 해당 경우를 처리 할 수 있다.

def BFS(G, v):
	# 방문체크를 위한 visited와 queue 생성
	visited = [0] * n
	queue = []

	# 시작점을 queue에 넣는다
	queue.append(v)
	visited[v] = True

	# queue가 비어있지 않으면 반복
	while queue:
		# queue의 첫번째 원소 반환
		t = queue.pop(0)
		
		# 현재 정점과 연결된 정점중 방문하지 않은 곳을 queue에 넣는다
		# queue에 넣음과 동시에 바로 방문체크를 한다.
		for i in G[t]:
			if not visited[i]:
				queue.append(i)
				visited[t] = True

 

추가 설명

• BFS는 정점 간의 거리가 모두 1인 경우 최단거리를 구하는 데 사용할 수 있다. 최단거리를 구하기 위해서 que에 원소를 삽입할때 거리정보도 같이 넣고 다음 정점을 푸시할때 위에서 구한 거리 + 1을 해주면 된다.