너비 우선 탐색 (BFS / breadth-first search)

그래프

연결의 집합을 모형화한 것. 정점(node)와 간선(edge)로 이루어진다.


┌───────┐   edge    ┌──╌────┐
| node1 |──────────>| node2 |
└───────┘           └───────┘

//node2는 node1의 이웃이다.

정점은 여러 개의 다른 정점과 바로 이어질 수 있다. 이렇게 바로 이어진 정점을 이웃(neighbor)라고 한다.

너비 우선 탐색

그래프를 대상으로 하는 종류의 알고리즘이다. 아래와 같은 질문에 대답하는데 도움이 된다.

정점1에서 정점2로 가는 경로가 존재하는가?
- 네트워크 내 정점2가 있는가
- 목표에 도달할 때까지 전체 네트워크를 탐색하게 된다.

정점1에서 정점2로 가는 최단 경로는 무엇인가?
- 너비 우선 탐색이 진행 될수록 탐색 범위는 출발점에서 멀어진다.
- 가까운 관계를 우선 탐색하고 없을시 다음 관계를 탐색
- 탐색 목록에 다음 관계를 추가하기 전에 가까운 관계를 모두 추가한다.
  - 이 방법은 순서대로 찾을 때만 가능하다. (목록에 더해진 대로..)
  - 큐(queue) 또는 대기열 자료구조가 사용된다.

큐(queue)

큐는 큐 안의 원소에 임의로 접근할 수 없다는 점에서 스택과 비슷하다. 삽입(enqueue)와 제거(dequeue) 두 가지 연산이 있다. 먼저 삽입된 항목이 먼저 제거되는 선입 선출(FIFO - first in first out) 자료구조이다. (반대로 스택은 후입 선출인 LIFO - last in first out 자료구조이다.)

그래프의 구현

정점으로 이루어진 그래프를 코드로 구현할 시, 관계를 표시하는 자료구조로 해시 테이블을 사용할 수 있다.

graph = {}
graph["you"] = ["alice","bob", "claire"]  ## you의 모든 이웃
graph["bob"] = ["anuj","peggy"]
graph["anuj"] = []
graph["claire"] = ["tom","john"]

##해시 테이블은 순서를 가지지 않기 때문에 키/값 쌍을 어떤 순서로 추가하든 상관없다.

anuj는 bob의 이웃이지만 bob은 anuj의 이웃이 아니다. (anuj로부터 누군가를 향해 나아가는 화살표가 없다.) 이렇게 방향을 가지는 그래프를 방향 그래프(directed graph)라고 한다. 무방향 그래프(undirected graph)는 화살표(방향성)을 가지지 않기 때문에 이어진 두 정점은 서로 이웃이 된다.

//방향그래프
┌──╌────┐           ┌──╌────┐
| node1 |──────────>| node2 |
└───────┘           └───────┘
//node2는 node1의 이웃이다.
//node1은 node2의 이웃이 아니다.

//무방향그래프
┌──╌────┐           ┌──╌────┐
| node1 |───────────| node2 |
└───────┘           └───────┘
//node2와 node1은 서로 이웃이다.

알고리즘의 구현

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

확인할 요소의 목록을 넣을 큐를 준비한다.
큐에서 하나의 요소를 꺼낸다.
해당 요소가 찾는 값인지 확인한다.
찾는 값인 경우 : 작업완료
찾는 값이 아닌 경우 : 해당 요소의 이웃을 모두 큐에 추가한다.
반복한다.
큐가 비어있다면 네트워크에는 찾고자 하는 값이 없다 : 작업종료


from collection import deque    ## 파이썬에서는 양방향 큐인 deque함수를 사용할 수 있다.
search_queue = deque()                      # 새 큐 생성
search_queue += graph["you"]                # 모든 이웃을 탐색 큐에 추가
searched = []                               # 이미 확인한 값을 추적하기 위한 것

while search_queue :                        # 큐가 비어있지 않는 한 계속 실행
    element = search_queue.popleft()        # 큐의 첫번째 값을 꺼냄
    if not element in searched :            # 이전에 확인하지 않은 값만 체크
        if element_is_the_one(element) :    # 찾는 값인지 확인
            print element + " is the one!"  # 값을 찾았고 작업 완료 -- 종료
            return true
        else :
            search_queue += graph[element]  # 원하는 값이 아님. 모든 이웃을 탐색 목록에 추가
            searched.append(element)        # 확인한 목록에 추가
return false                                # 도달했다는 것은 찾는 값이 없다는 것을 의미 -- 종료

특정 값을 확인하고 나면, 그 값이 다시 탐색되지 않도록 표시를 해야 한다. 그렇지 않으면 무한 반복에 빠질 수도 있다.

큐에서 삽입/삭제 대신 푸시(push)와 팝(pop)을 용어로 사용하는 경우도 있다.

실행시간

원하는 값을 찾기 위해 네트워크 전체를 탐색한다는 것은 모든 정점을 따라 움직인다는 뜻이 된다. 그러므로 실행시간은 최소한 O(간선의 개수)가 된다.

탐색할 요소를 저장하는 큐도 있어야 한다. 큐에 사람을 추가하는 데는 상수시간, 즉 O(1)이 걸리므로 모든 사람에 대해 이것을 적용하면 총 O(사람의 수) 시간이 걸린다.

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

reference

도서 : Hello Coding 그림으로 개념을 이해하는 알고리즘

알고리즘 너비우선탐색