[알고리즘] 그래프 너비 우선 탐색(Breadth-First Search)

너비 우선 탐색(Breadth-First Search) 란?

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

 

너비 우선 탐색(Breadth-First Search) 이해

위와 같은 형태의 그래프가 있을 때 넓이 우선 탐색은 처음 시작 정점을 방문한 뒤, 정점에서 인접한 모든 정점을 방문한다.

다른 모든 정점들에 대해서도 방문하지 않은 정점이 없어질 때 까지 반복한다. 넓이 우선 탐색은 선입선출원칙을 기반으로 한 탐색법이기 때문에 큐를 이용한다.

 

첫 번째 노드에서 출발하기 때문에 1번 노드를 방문예약(need_visit)에 넣은 뒤 1번 노드를 방문예약큐에서 빼고 인접한 노드인 2, 5번 노드를 방문예약에 넣어준다.

 

방문예약큐 가장위에있는 2번노드를 큐에서 뺀 뒤 2번 노드와 인접한 노드인 1, 3번 노드를 방문예약큐에 넣어준다.

 

마찬가지로 5번 노드를 빼고 5번노드와 인접한 1, 6, 8번 노드를 방문노드큐에 넣어준다.

 

1번 노드는 이미 방문했던 노드니까 방문노드큐에서 빼기만 하고 바로 3번노드를 빼준다. 이 후 같은방식으로 2, 4번 노드를 방문예약큐에 넣어준다.

같은 방식으로 계속 수행하면

 

 

 

 

더이상 방문예약큐에 남아있는 정점이 없을 때 탐색을 종료한다.

 

너비 우선 탐색(Breadt-First Search) 구현

def bfs(graph, start_node):
    visited, need_visit = list(), 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

 

너비 우선 탐색(Breadt-First Search) 시간 복잡도

• 노드 수: V
• 간선 수: E
• 너비 우선 탐색의 시간 복잡도는 노드 수 + 간선 수로 표현된다. O(V+E)