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

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

Copy
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

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

Copy
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는 레벨별 탐색을 통해 넓은 범위의 노드들을 효과적으로 탐색할 수 있습니다.