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

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

• 노드와 같은 레벨에 있는 형제 노드들부터 먼저 탐색하는 방식
• 그래프를 표현 할 때 딕셔너리와 리스트 자료 구조 활용
• 시간 복잡도 : O(V+E), (V: 노드 갯수, 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']

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')

Out[11]:

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

 

GitHub - DAWUNHAN/Algorithms-and-DataStructure: Algorithms and DataStructure with Python