BFS 기본 구현

BFS (Breath First Search) :
  - 같은 깊이에 있는 노드들을 탐색하고 그와 연결된 다음 깊이의 노드들을 탐색하는 기법
* visited, need_visit 두 개의 큐를 사용
* 시간 복잡도: O(N+E) (N: 노드 수, E: 간선 수) 

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']
"""
{
    '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']
}
"""

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

print(bfs(graph, 'A')) 

""" ['A', 'B', 'C', 'D', 'G', 'H', 'I', 'E', 'F', 'J'] """

출처 : FASTCAMPUS