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

• 그래프에서 시작 노드에 인접한 노드부터 탐색하는 알고리즘
• BFS알고리즘은 모든 간선의 비용이 동일한 조건에서 최단 거리를 구하는 문제에 효과적인 알고리즘
• 미로를 빠져나가는 최단 거리 구하는 문제등에서 효과적인 알고리즘

과정

1. 시작 노드를 큐(Queue)삽입하고 방문처리

2. 큐에있는 노드를 꺼내어 방문하지 않은 인접 노드를 큐에 삽입 후 방문 처리

3. 2번 과정을 반복 (방문처리된 노드는 큐에 넣지 않습니다.)

4. 큐에 넣을 노드가 없으면 큐에서 차례대로 꺼내어 방문처리

알고리즘 구현

# queue 구현을 위한 deque을 사용
from collections import deque

visited = [False] * 8
graph = [
    [],
    [2,3],      #1
    [1,4,5],    #2
    [1,4,6],    #3
    [2,3,5,7],  #4
    [2,4,7],    #5
    [3,7],      #6
    [4,5,6],    #7
]

def bfs(graph, start, visited):
    #시작 노드를 큐에 저장
    queue = deque([start])
    # 현재 노드를 방문 처리
    visited[start] = True
    
    while queue:
        popNode = queue.popleft()
        print(popNode, end = ' ')
        for nearlyNode in graph[popNode]:
            if not visited[nearlyNode]:
                queue.append(nearlyNode)
                visited[nearlyNode] = True
                
                
bfs(graph=graph,start=1,visited=visited)