BFS

• BFS

  • 너비 우선 탐색, 가까운 노드부터 우선적으로 탐색하는 알고리즘 

  • 큐(queue) 자료 구조를 이용함

  • 은행 대기줄과 비슷

  • 먼저 들어온 데이터가 먼저 나옴

  • deque를 사용함

  • popleft: 처음 입력한 원소 삭제

• 그래프로 보기

그래프

• 1→2→3→8→2을 popleft시키고 2와 인접한 노드 보기→7→3을 leftpop시키고 3과 인접한 노드 보기→4→5→6

• 코드로 보기

from collections import deque
def bfs(graph, start, visited):
  queue = deque([start])
  visited[start] = True
  while queue:
    v=queue.popleft()
    print(v,end=' ')
    for i in graph[v]:
      if not visited[i]:
        queue.append(i)
        visited[i]=True
graph = [[],[2,3,8],[1,7],[1,4,5],[3,5],[3,4],[7],[2,6,8],[1,7]]
visited = [False]*9
bfs(graph, 1,visited)