BFS (Breadth-First Search)

• BFS는 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다.
• BFS는 큐 자료구조를 이용한다.
  
  1.  탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
  2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리한다.
  3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.
  4.  

---

1. BFS 동작예시

출처 : 이코테2021

시작지점은 1이며 인접한게 여러개이면 번호가 낮은 노드를 가도록 해보자.

 

 

큐에서 1을 꺼내서 인접한 노드 '2', '3', '8'을 큐에 삽입하고 방문처리를 해준다.

 

그다음 인접한 '2'로 가서 큐에서 2를 꺼내고 2와 인접한 '7'를 방문처리한다.

 

마찬가지로 큐에서 3을꺼내고 인접한 4와 5노드를 방문처리를 한다.

 

그 다음 큐에서 8을 꺼냈는데 인접한 노드가 없다면 무시하고 다음으로 진행한다.

 

탐색순서는 이와같다.

'1'과 거리가 1인 2,3,8

'1'과 거리가 2인 7,4

등으로 탐색이 진행됐다.

---

2. 소스코드

from collections import deque

def DFS(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

• 큐 라이브러리를 사용하기위해 queue = deque를 선언했다.

#0인덱스가 아닌 1번부터 시작하는 경우가 많아 예시를 0번을 비워뒀다. []
graph = [
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

#각 노드가 방문된 정보를 표현
#모든 노드를 방문하지 않은 False로 표현
visited = [False] * 9

DFS(graph, 1, visited)

#출력 결과
1 2 3 8 7 4 5 6