BFS (Breadth-first search)

• 대표적인 그래프 탐색 알고리즘
• 정점들과 같은 레벨에 있는 노드들을 먼저 탐색하는 방식

• BFS 방식: A - B - C - D - G - H - I - E - F - J

  • 한 단계씩 내려가면서, 해당 노드와 같은 레벨에 있는 노드들 (형제 노드들)을 먼저 순회

• DFS 방식: A - B - D - E - F - C - G - H - I - J

  • 한 노드의 자식을 타고 끝까지 순회한 후, 다시 돌아와서 다른 형제들의 자식을 타고 내려가며 순회

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

BFS 알고리즘 구현

• 두개의 자료구조 큐를 활용한다!
• need_visit, visited 두개의 큐를 생성

• 파이썬에서는 다음과 같이 간단하게 구현할 수 있다.

def bfs(graph, start_node):
    visited = list()
    need_visit = list()
    
    need_visit.append(start_node)
    
    while need_visit:
        node = need_visit.pop(0)
        if node not in visited:
            visited.append(node)
            need_visit.extend(graph[node])
    
    return visited

bfs(graph, 'A')

시간 복잡도

• 노드 수 : V

• 간선 수 : E

  • 위 코드에서 while need_visit은 V+E 번 만큼 코드를 수행한다. (총 19번)
• 시간 복잡도 : O(V+E)