너비 우선 탐색

너비 우선 탐색 Breath-First Search

두 항목 간의 최단 경로를 찾는다.

너비 우선 탐색은 두 가지 질문에 대답할 수 있다.

질문 1. 정점 A에서 정점 B로 가는 경로가 존재하는가?

질문 2. 정점 A에서 정점 B로 가는 최단 경로는 무엇인가?

망고 판매상 찾기 문제 (질문 1. 나의 네트워크에 망고 판매상이 있는가?)

나는 망고 농장의 주인이다.

망고를 팔기 위해 페이스북 친구 목록 중 망고 판매상을 찾으려고 한다.

먼저, 페이스북 친구 목록을 살펴보았다.

그런데, 친구 중에 망고 판매상이 없다.

이제 친구의 친구를 찾아볼 차례이다.

만약 앨리스가 망고 판매상이 아니면 앨리스의 친구를 목록에 올린다.

앨리스의 친구, 앨리스의 친구의 친구, 이런식으로 망고 판매상을 찾을 때까지 전체 네트워크를 탐색하게 된다.

망고 판매상 찾기 문제 (질문 1. 누가 가장 가까운 망고 판매상인가?)

친구의 친구의 친구보다는 친구의 친구가 낫고, 친구의 친구보다는 친구가 낫다.

가장 가까운 망고 판매상을 찾기 위해서는, 2촌 관계를 추가하기 전에 1촌 관계를 탐색 목록에 모두 추가한다.

이를 위한 자료구조가 큐이다.

큐는 선입선출 FIFO 자료구조이다.

그래프의 구현

우선 코드로 그래프를 구현한다.

나->친구들 같은 관계를 표현하기에 좋은 자료구조로는 해시 테이블이 있다.

graph = {}

graph["you"] = ["alice", "bob", "claire"]

다음 그림처럼 큰 그래프를 표현해보자.

graph = {}

graph["you"] = ["alice", "bob", "claire"]

graph["bob"] = ["anuj", "peggy"]

graph["alice"] = ["peggy"]

graph["claire"] = ["thom", "jonny"]

graph["anuj"] = []

graph["peggy"] = []

graph["thom"] = []

graph["jonny"] = []

>해시 테이블은 순서를 가지지 않기 때문에 각 행의 순서는 상관없다.

>아누지는 밥의 이웃이지만 밥은 아누지의 이웃이 아니다. (인스타그램 팔로우처럼 말이다. 맞팔로우가 되어있지 않는 이상..)

그러므로, 이 그래프는 방향을 가지는 방향 그래프 directed graph 이다.

알고리즘의 구현

알고리즘이 구현되는 방식은 다음과 같다.

양방향 큐 deque를 이용하여 구현한다.

from collections import deque

graph = {}

graph["you"] = ["alice", "bob", "claire"]

graph["bob"] = ["anuj", "peggy"]

graph["alice"] = ["peggy"]

graph["claire"] = ["thom", "jonny"]

graph["anuj"] = []

graph["peggy"] = []

graph["thom"] = []

graph["jonny"] = []

search_queue = deque() #새 큐를 생성

search_queue += graph["you"] #모든 이웃을 탐색 큐에 추가

while search_queue: #큐가 비어 있지 않는 한 계속 실행

person = serach_queue.popleft() #큐의 첫 번째 사람을 꺼냄

if person_is_seller(person): #망고 판매상인지 확인

print person + "is a mango seller!"

return True

else:

search_queue += graph[person] #망고 판매상이 아니면 모든 이웃을 탐색 목록에 추가

return False #망고 판매상이 아무도 없다.

def person_is_seller(name):

return name[-1] == 'm'

사람의 이름이 m으로 끝나면 망고 판매상이라고 가정하였다.

한 사람이 큐에 여러번 있으면 무한 반복에 빠질 수 있다.

따라서, 이미 확인한 사람의 명단을 가진 코드를 다시 작성한다.

from collections import deque

graph = {}

graph["you"] = ["alice", "bob", "claire"]

graph["bob"] = ["anuj", "peggy"]

graph["alice"] = ["peggy"]

graph["claire"] = ["thom", "jonny"]

graph["anuj"] = []

graph["peggy"] = []

graph["thom"] = []

graph["jonny"] = []

def search(name):

search_queue = deque() #새 큐를 생성

search_queue += graph["you"] #모든 이웃을 탐색 큐에 추가

searched = []

while search_queue: #큐가 비어 있지 않는 한 계속 실행

person = search_queue.popleft() #큐의 첫 번째 사람을 꺼냄

if not person in searched:

if person_is_seller(person): #망고 판매상인지 확인

print person + " is a mango seller!"

return True

else:

search_queue += graph[person] #망고 판매상이 아니면 모든 이웃을 탐색 목록에 추가

searched.append(person)

return False #망고 판매상이 아무도 없다.

def person_is_seller(name):

return name[-1] == 'm'

search("you")

실행시간

망고 판매상을 찾기 위해 네트워크 전체를 탐색한다는 것은 

모든 정점을 따라서 움직인다는 뜻이 된다.

즉, 실행시간은 최소한 O(간선의 개수)가 된다.

그리고 탐색할 사람을 저장하는 큐도 있어야 한다.

큐에 사람을 추가하는 데는 상수시간 O(1)이 걸린다.

즉, 모든 사람에 대해 O(사람의 수)시간이 걸린다.

따라서, 너비 우선 탐색은 O(사람의 수 + 간선의 수) 가 되고, O(V+E)로 표기한다.