(알고리즘) 너비우선탐색 (BFS)

1. BFS 와 DFS 란?

• 대표적인 그래프 탐색 알고리즘
  • 너비 우선 탐색 (Breadth First Search): 정점들과 같은 레벨에 있는 노드들 (형제 노드들)을 먼저 탐색하는 방식
  • 깊이 우선 탐색 (Depth First Search): 정점의 자식들을 먼저 탐색하는 방식

BFS/DFS 방식 이해를 위한 예제

• BFS 방식: A - B - C - D - G - H - I - E - F - J
  • 한 단계씩 내려가면서, 해당 노드와 같은 레벨에 있는 노드들 (형제 노드들)을 먼저 순회함
• DFS 방식: A - B - D - E - F - C - G - H - I - J
  • 한 노드의 자식을 타고 끝까지 순회한 후, 다시 돌아와서 다른 형제들의 자식을 타고 내려가며 순화함

 

 

2. 파이썬으로 그래프를 표현하는 방법

• 파이썬에서 제공하는 딕셔너리와 리스트 자료 구조를 활용해서 그래프를 표현할 수 있음

그래프 예와 파이썬 표현

해쉬의 키에는 노드, 밸류에는 그 노드의 인접정점을 적어준다. 

 

graph = dict()

graph['A'] = ['B', 'C']
graph['B'] = ['A', 'D']
graph['C'] = ['A', 'G', 'H', 'I']
graph['D'] = ['B', 'E', 'F']
graph['E'] = ['D']
graph['F'] = ['D']
graph['G'] = ['C']
graph['H'] = ['C']
graph['I'] = ['C', 'J']
graph['J'] = ['I']

3. BFS 알고리즘 구현

• 자료구조 큐를 활용함
  • need_visit 큐와 visited 큐, 두 개의 큐를 생성 (DFS에선 스택 하나 큐 하나를 생성한다)

1 - 1. 가장 상단의 노드를 need_visit queue에 넣는다.  

1 - 2. need_visit queue의 0번째 값을 pop하여 node에 넣는다. 

1 - 3. visited queue에 A가 있는지 확인 후 없으면 넣는다. 그리고 A키에 해당되는 밸류를 need visit queue에 넣는다. 

2 - 1. 다시 반복. need visit queue의 0번째 값 pop하여 node에 넣는다.

 

2 -2. visited queue에 B가 있는지 확인 후 없으면 넣는다. 그러고 B의 밸류값을 need visit queue에 넣는다.

위의 순서를 계속 반복한다. 

코드로 나타내보면 아래와 같다.

 

def bfs(graph, start_node):
    visited = list()
    need_visit = list()
    
    need_visit.append(start_node)
    
    while need_visit:
        node = need_visit.pop(0)  # pop(0)이라고 하면 맨앞에 있는 애를 빼고 뒤에 애들을 앞으로 땡긴다
        if node not in visited:
            visited.append(node)
            need_visit.extend(graph[node])
    
    return visited

 

4. 시간 복잡도

• 일반적인 BFS 시간 복잡도
  • 노드 수: V
  • 간선 수: E
    • 위 코드에서 while need_visit 은 V + E 번 만큼 수행함
  • 시간 복잡도: O(V + E)