BFS 넓이 우선 탐색- 1분 정리

BFS 넓이 탐색이란 그래프에서 가까운 노드부터 우선적으로 탐색을 하는 알고리즘을 말한다. 여기서 탐색이란 여러 데이터 중에서 내가 찾고 싶은 데이터를 추출하는 것을 말한다.

 

BFS는 큐 자료구조를 이용해서 구현할 수 있다.

 

넓이 우선 탐색은 다음과 같은 과정을 거치게 된다.

 

1. 시작 노드를 큐에 삽입을 하고 방문처리를 한다.

2. 큐에서 노드를 꺼내 방문하지 않은 인접한 모든 노드를 큐에 삽입한다. (큐에 삽입과 동시에 방문처리를 한다.)

3. 큐가 빌 때까지 2번 과정을 반복하면 된다.

 

다음의 그래프를 살펴보자!

 

 

다음과 같은 그래프가 준비되어 있다. 시작 노드 1을 큐에 삽입, 방문처리와 함께 bfs 알고리즘이 시작이 되게 된다. 이제 큐에서 매번 노드를 꺼내 방문하지 인접하지 않은 노드가 있는지 확인하고 있는 것이 확인이 된다면 큐에 삽입을 한다. 

 

 

 

 

이러식으로 큐가 빌때 까지 반복한다. 

 

 

 

그럼 방문하는 노드의 순서는 1 -> 2 -> 3 -> 8 -> 7 -> 4 -> 5 -> 6 이런 식으로 탐색을 진행을 하게 된다. 파이썬 코드로 구현하면 다음과 같다. 

 

from collections import deque #큐 구현을 위해서 덱스 사용 할 거임

graph= [
  [],
  [2,3,8],
  [1,7],
  [1,4,5],
  [3,5],
  [3,4],
  [7],
  [2,6,8],
  [1,7]
]

visited = [False] * 9 # 0부터 9까지 이니까 총 9개를 사용을 해야 함

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 visited[i]==False:
        queue.append(i)
        visited[i]=True
        
  
bfs(graph,1,visited)