[day25] BFS 기초 (1)

😎 BFS (Breadth-First Search)

BFS는 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다.

여기서 가장 가까운 노드란 해당 노드와 같은 레벨에 있는 노드들(형제 노드)을 먼저 순회하는 방식이다.

BFS는 "큐" 자료구조를 이용한다. 큐는 FIFO의 질서를 가지는 자료구조이다.

 

😎 BFS 구현 필수 요소 3가지

1. start Node	루트노드같은 시작 노드가 필요하다.
2. visited Nodes	탐색을 중복하지 않도록 visited노드이면 패스한다. 이를 위해 해당 노드가 visited인지 기억을 해놓는다.
3. queue	popLeft가 필요하기 때문에 python에서는 deque를 활용한다.

 

 

 

from collections import deque

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

def bfs(graph, start, visited):
  #1.queue에 첫 노드부터 삽입
  queue = deque([start])
  #2. 방문한 노드 기억
  visited[start] = True
  #3. queue가 바닥날때까지 반복
  while queue:
    #4. queue의 첫번째 원소 pop
    v = queue.popleft()
    # print(v, queue)
    #5. 순차적으로 graph 순회
    for i in graph[v]:
      #6. 방문하지 않은 노드가 있는 경우 queue에 삽입
      if not visited[i]:
        queue.append(i)
        #7. 방문한 노드 기억
        visited[i] = True

visited = [False] * 9 
print(bfs(graph, 1, visited))


# 1 deque([])
# 2 deque([3, 8])
# 3 deque([8, 7])
# 8 deque([7, 4, 5])
# 7 deque([4, 5])
# 4 deque([5, 6])
# 5 deque([6])
# 6 deque([])