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

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

대표적인 그래프 탐색 알고리즘인 너비 우선 탐색에 대해서 알아본다.

image-20201118235208216

BFS 구현 방법

key valuess        
A B C      
B A D      
C A G H I  
D B E F    
E D        
F D        
G C        
H C        
I C J      
J I        
graph_list = {'A':(['B','C']),
              'B':(['A','D']),
              'C':(['A','G','H','I']),
              'D':(['B','E','F']),
              'E':(['D']),
              'F':(['D']),
              'G':(['C']),
              'H':(['C']),
              'I':(['C','J']),
              'J':(['I'])}

BFS 알고리즘 코드

앞으로 base로 쓸 bfs 함수 코드를 정리한다.

from collections import deque

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

    while need_visit:
        node = need_visit.popleft()
        if node not in visited:
            visited.append(node)
            need_visit.extend(graph_list[node])

    return visited

BFS 알고리즘 코드2 (코드 더 개선 필요)

from collections import deque
def bfs(graph_list, start_node):
    visited = []
    need_visit = deque([start_node])

    while need_visit:
        node = need_visit.popleft()
        if node not in visited:
            visited.append(node)
            need_visit.extend([ m for m in graph_list[node] if m not in visited])

    return visited

결과

start_node = 'A'
print(bfs(graph_list, start_node))
# ['A', 'B', 'C', 'D', 'G', 'H', 'I', 'E', 'F', 'J']