[알고리즘] BFS

BFS (Breadth-First Search)

너비 우선 탐색으로, 가까운 노드부터 탐색하는 알고리즘.
정점들과 같은 레벨에 있는 형제 노드들을 먼저 탐색.

A-B-C-D-G-H-I-E-F-J 순으로 순회.
한 단계씩 내려가면서, 해당 노드와 같은 레벨에 있는 노드들을 먼저 순회한다.

알고리즘 구현

: 큐 자료구조를 활용.

1) 탐색 시작 노드를 큐(need_visit)에 삽입하고, 방문처리(need_visit큐에서 꺼낸 후, visited 큐에 삽입)한다.

2) 해당 노드의 인접 노드를 모두 큐(need_visit)에 삽입한다.

3) 최상단 노드를 큐(need_visit)에서 꺼낸 후, 방문한 적이 없으면 방문처리한다.
need_visit이 빌 때까지 2)-3) 반복.

*방문한 적이 있으면 다음 최상단 노드를 큐(need_visit)에서 꺼낸 뒤, 비교한다.

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

• deque 라이브러리 사용

from collections import deque

def bfs(graph, start_node, visited):
    # 큐 구현을 위해 deque 라이브러리 사용
    need_visit = deque([start_node])
    # 현재 노드를 방문 처리
    visited[start_node] = True
    
    # 큐가 빌 때까지 반복
    while queue:
    	# 큐에서 하나의 원소를 뽑아 출력
        cur_node = need_visit.popleft()
        print(cur_node, end=' ')
        # 해당 원소와 연결된, 방문 안한 원소들을 큐에 삽입
        for node in graph[cur_node]:
            if not visited[node]:
            	need_visit.append(node)
                visited[node] = True
                
# 각 노드가 방문된 정보를 리스트 자료형으로 표현
visited = [False] * len(graph)
# 함수 호출
bfs(graph, start_node, visited)

시간 복잡도

: O(V+E)
노드 수(V)와 간선 수(E)를 더한 만큼 수행함

참고) Dave LEE 강의, <이것이 코딩 테스트다> 서적