BFS

p.146

 

BFS(Breadth First Search) : 너비 우선 탐색

* 큐를 사용(deque)

* graph를 인접 리스트 사용

* visited로 방문했는지 여부 확인

 

[동작 과정]

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리

2. 큐에서 popleft()를 하여 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 큐에 append

3. 2번 과정을 더 이상 수행할 수 없을 때까지 반복

 

 

from collections import deque

def bfs(graph, start, visited):
  queue=deque()
  queue.append(start)
  visited[start]=True

  # queue가 빌 때까지 반복
  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)

 

[결과]

1 2 3 8 7 4 5 6