그래프 - BFS 구현

BFS 알고리즘 구현

큐 자료구조 활용

• need_visit queue
• visited queue

 

개념

위 그래프에 대해 BFS를 구현한다면 다음과 같은 순서로 진행된다.

 

1. 제일 처음 노드 A를 need_visit queue에 추가한다. (시작)

2. need_visit queue에서 dequeue 한 뒤 temp_node로 가져온다.
    (코드에선 list를 사용하기 때문에 pop(0)을 통해 dequeue했다.)

3. temp_node가 visited queue에 존재하는지 확인

4-1. 없다면 visited queue에 A를 추가

4-2. 존재한다면 아무것도 하지 않고 2번부터 다시 시작

5. temp_node였던 A를 graph_dict에서 key로 찾아 나온 value를 need_visit queue에 추가한다.
    (list뒤에 list를 붙여 하나의 list로 만드는 것이기에 extend 함수를 사용한다.)

6. need_visit queue가 빌 때 까지 2~5번 과정 반복
    (빈 list []에 대해선 if list를 했을 때 False 가 나오는 점을 이용)

7. visited queue 리턴 (끝)

 

그렇게 위와 같은 과정을 거치게 되며

그 결과 완성된 visited queue를 얻을 수 있다.

 

코드

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']

def bfs(graph, start_node):
  visited = []
  need_visit = []

  need_visit.append(start_node)
  while need_visit:
    temp_node = need_visit.pop(0)
    if temp_node not in visited:
      visited.append(temp_node)
      need_visit.extend(graph[temp_node])  # append가 아닌 extend 사용
  return visited

print(bfs(graph, 'A))

 

시간복잡도

노드 수: V

간선 수: E

라고 칭할 때 

while need_visit은 V + E번 만큼 수행함으로

시간복잡도는 O(V+E)가 된다.