BFS(너비 우선 탐색) Python코드로 이해하기

 

BFS(너비 우선 탐색)

시작 노드부터 출발해서 가까운 노드부터 우선적으로 탐색하는 형태

큐 자료 구조를 이용한다는 점이 특징

 

1. 시작 노드를 큐에 넣고 방문 처리를 해야 합니다. 
2. 큐에서 노드를 꺼낸 뒤에 그 꺼낸 노드에 인적 노드 중에서 방문하지 않은 노드를 모두 취해놓고 방문 처리를 수행.
   bfs는 해당 시점에서 인접한 노드를 한 번에 전부 큐에 넣는다는 점이 특징

큐를 위해서 하나의 deque 라이브러리를 부르자.
dfs 때와 마찬가지로 이 0번 노드에 대한 내용을 비우고 8개의 노드를 모두 처리할 수 있도록 총원소가 9개인 리스트 객체를 만들어 그래프를 표현해준다.
그래서 1번 노드는 2, 3, 8번 노드와 인접해 있고 2번 노는 1, 7번 노드와 인접해있다. 
방문 처리 목적으로 visited라는 이름의 하나의 리스트도 만들어주자.

시작 노드를 이와 같이 큐에 넣어 방문 처리한 뒤에 이외에 큐가 빌 때까지 즉, 더 이상 수행할 수 없을 때까지 반복한다.

매번 큐에서 하나의 원소를 꺼내고 deque을 이용해 q를 구현할 때는 popleft를 이용해 가장 먼저 들어왔던 원소를 꺼낼 수 있다. 
그래서 이렇게 큐에서 요소를 꺼낸 뒤에 해당 노드의 번호를 출력해 주고,

그 다음에 그 꺼낸 노드와 인접한 노드를 하나씩 확인하면서 아직 방문하지 않은 게 있다면 큐에 다 넣어줄 수 있도록 한다.