BFS(Breadth-First Search)

📖Graph

📖BFS(Breadth-First Search)

시작 노드에 인접한 노드부터 탐색하는 그래프 순회 방법

📖특징

• 직관적이지 않음
• 시작 노드에서 시작해서 거리에 따라 단계별로 탐색
• 재귀적으로 동작하지 않음
• 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 Queue를 사용 → FIFO 원칙으로 탐색

📖과정

1. 시작 노드를 방문해 큐에 삽입하고 방문 처리
2. 큐에서 노드를 꺼내 해당 노드에 방문하지 않은 인접 노드 정보를 전부 큐에 삽입하고 방문 처리

• 해당 인접 노드들 전부 방문 처리

3. 2번 과정을 더 이상 수행할 수 없을 때(큐에 노드가 하나도 없을 때)까지 반복

📖구현

📎Queue

from collections import deque
 
def bfs(graph, start):
    queue = deque([start])
    visited = []
    
    while queue:
        node = queue.popleft()
        visited.append(node)
        
        for adj in graph[node]:
            if adj in not visited:
                queue.append(adj)

• visited에 탐색 순서대로 노드가 들어감

📖시간 복잡도

그래프 구현 방법	시간복잡도
인접 행렬	O(n²)
인접 리스트	O(n+e)

📖BFS & DFS