BFS (너비우선탐색)

BFS 는 DFS 똑같이 완전탐색 알고리즘의 한 종류인데 다른접이 있습니다. BFS 같은 경우 너비우선탐색이라고 큐를 사용해서 탐색한다.

넓고 퍼져나가는 형태로 탐색

ex) DFS (Parent Node기준 무조건 작은 Child Node가 먼저)

0 > 1 > 3 > 7

3 > 8

1 > 4 > 9

0 > 2 > 5

2 > 6 > 10

6 > 11

6 > 12

ex) BFS (Parent Node기준 Child Node가 좌우)

0 > 1 , 2

1 > 3 , 4

2 > 5 , 6

3 > 7, 8

4 > 9

5

6 > 10 , 11, 12

BFS 예제

from collections import deque

adj = [[0] * 13 for _ in range(13)]
adj[0][1] = adj[0][2] = 1
adj[1][2] = adj[1][4] = 1

# for row in adj:
#     print(row)

def bfs():
    dq = deque()
    dq.append(0)
    while dq:
        now = dq.popleft()
        for nxt in range(13):
            if adj[now][nxt]:
                dq.append(nxt)


bfs()