BFS 알고리즘은 '너비 우선 탐색'이라는 의미를 가진다. 가까운 노드부터 탐색하는 알고리즘이다. DFS는 멀리있는 노드를 우선적으로 탐색하는 방식으로 동작하지만, BFS는 그 반대이다. 시간 복잡도는 O(N) 이다.
BFS 예제
from collections import deque
#BFS 메서드 정의
def dfs(graph,start,visited):
#큐(Queue)구현을 위해 deque 라이브러리 사용
queue=deque([start])
visited[start]=True
#큐가 빌 때까지 반복
while queue:
v=queue.popleft()
print(v,end='')
#해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
for i graph[v]:
if not visited[i]:
queue.append(i)
visited[i]=True
#2차원 리스트
...
visited=[False]*9
#BFS 호출
bfs(graph,1,visited)
글 재미있게 봤습니다.