본문으로 건너뛰기

너비 우선 탐색(BFS) 구현 방법

너비 우선 탐색(BFS) 구현 방법

1. 큐 사용: BFS는 큐를 사용하여 탐색할 노드들을 관리합니다. 큐를 사용하여 각 레벨별로 노드를 순차적으로 탐색합니다.

큐 사용 예시
def bfs(graph, start):
visited = []
queue = [start]

while queue:
node = queue.pop(0)
if node not in visited:
visited.append(node)
# 리스트를 이용하여 중복 제거
queue.extend([n for n in graph[node] if n not in visited])

return visited

2. 레벨별 탐색: BFS는 각 노드의 레벨별로 인접 노드를 탐색합니다. 이는 큐의 선입선출(FIFO) 특성을 활용합니다.

레벨별 탐색 예시
while queue:
node = queue.pop(0)
if node not in visited:
visited.append(node)
# 리스트를 이용하여 중복 제거
queue.extend([n for n in graph[node] if n not in visited])

시간 복잡도

  1. 시간 복잡도: (O(V + E))

    • 여기서 V는 정점의 수, E는 간선의 수를 나타냅니다. 각 정점은 한 번씩 방문되며, 각 간선은 한 번씩 검사됩니다.
  2. 최단 경로 탐색: BFS는 무방향 그래프에서 시작 노드에서 목표 노드까지의 최단 경로를 찾는 데 효과적입니다.

  3. 넓은 범위 탐색: BFS는 레벨별 탐색을 통해 넓은 범위의 노드들을 효과적으로 탐색할 수 있습니다.