BFS

BFS란?

너비 우선 탐색( Breadth-First Search ): 그래프에서 가까운 부분을 우선적으로 탐색하는 알고리즘.

방문 처리, 큐, 큐 자료구조 이용

큐 : https://jun2ee22.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%81%90
그래프 자료구조 url

 

tip.1차원 배열이나 2차원 배열을 그래프 형태로 생각하면 수월함.

---

큐에 삽입(방문 처리)
-> 큐에서 pop(0) 후 해당 노드의 방문하지 않은 인접 노드를 큐에 모두 삽입(방문 처리)

 더 이상 수행할 수 없을 때까지 반복

방문 순서: 1 -> (1) -> 2 -> 4 -> (2) -> (4) -> 3 -> 5 -> (3) -> (5) 

---

ex) BFS

더보기

from collections import deque

# BFS 함수 정의
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 not visited[i]:
                queue.append(i)
                visited[i] = True
                
graph = [
    [],
    [2, 4],
    [1],
    [4, 5],
    [1, 3, 5],
    [3, 4]
]

visited = [False] * 6

bfs(graph, 1, visited)

 

---

이것이 코딩 테스트다 - 나동빈

정리하긔