[Graph] BFS 그래프 너비 우선 탐색과 최단 거리

너비 우선 탐색

각 정점을 방문할 때마다 모든 인접 정점들을 검사하는 알고리즘이다. 처음 보는 정점이 있다면 방문예정이라고 표시하고 별도의 위치에 저장한다.  인접한 정점들을 모두 검사하고 나면, 목록에서 다음 정점을 꺼내어 방문하게 된다.  이 목록은 FIFO의 큐형태를 지니게 될 것이다. 한가지 특징은 모든 정점을 탐색할 수 있다는 것이다.

알고리즘의 큰 틀

# 슈도 코드

# 인접 리스트 or 인접 행렬
adj = []
# 발견 리스트 - false 로 초기화
discovered = []
# 방문 예정 큐
que = deque()

def bfs(start):
# 1. 시작점을 발견하고 방문 예정에 푸쉬한다.
    discovered[start] = True
    que.append(start)
    
# 2. 방문 예정 목록이 고갈될 때까지 반복한다.
    while que:
# 3. 목록에서 방문해야하는 것을 꺼내 방문한다.
        here = que.popleft()
        ### logic ###
        
# 4. 인접 노드 중 아직 발견되지 않은 노드가 있었다면 발견표시하고 방문 예정에 푸쉬한다.        
        for there in adj[here]:
            if not discovered[here]:
                discovered[there] = True
                que.append(there)

시간 복잡도

DFS 알고리즘과 동일하다.  모든 노드가 호출되므로 시간복잡도는 O(|V|) 이고,  인접 노드를 검사하는 반복문을 포함해서 시간복잡도를 계산하면, 인접리스트로 구현했는지 인접행렬로 구현했는지에 따라 조금 다르다.

인접리스트로 구현한 경우 최종 시간 복잡도는 O(|V| + |E|). 인접행렬로 구현한 경우 최종 시간 복잡도는  O(|V|^2).

BFS 와 최단 거리

다양한 문제 풀이에 사용되는 DFS에 비해서 BFS는 대개 최단 경로 문제를 풀 때 사용된다. 

# 슈도 코드

# 인접 리스트 or 인접 행렬
adj = []
# start부터 index까지 최단 거리 - -1로 초기화
distance = []
# 방문 루트를 표시한 스패닝 트리 상 부모 노드 (루트인 경우 자기 자신)
parent = []
# 방문 예정인 목록
que = deque()

def bfs():
    distance[start] = 0
    parent[start] = start
    que.append(start)
    
    while que:
        here = que.popleft()
        
        for there in adj[here]:
            if distance[there] == -1:
                distance[there] = distance[here] + edge[here][there]
                parent[there] = here
                que.append(there)