BFS Algorithm (Breadth-First-Search, 너비 우선 탐색)

• BFS (너비 우선 탐색)

  : 현재 정점과 인접한 정점들에 대해 우선적으로 탐색하는 방식 => 넓게(wide) 탐색.
   큐(Queue)를 이용해서 구현.
   방문한 정점에 대해 표시하지 않는 경우, 무한루프에 빠질 가능성 有 => 각 정점의 기 방문 여부 저장 (visited)
   아래로 깊은 그래프에 대해 좋은 성능을 기대할 수 있다.
       ( -> 아래로 깊은 그래프에서 해가 중간에 있는 경우)

• BFS의 과정

출처 : https://gongbu-ing.tistory.com/58

 

• BFS 시간 복잡도 (DFS와 동일)

시간 복잡도 (N: 노드 수, E: 에지 수)

• 인접 행렬로 표현된 그래프 => O(N^2)
• 인접 리스트로 표현된 그래프 => O(N+E)

    희소 그래프 (Sparse Graph)의 경우, 인접리스트 사용이 유리

        -> 그래프 내에 적은 숫자의 간선만을 가지는 그래프

 

• DFS vs. BFS

출처 : https://devuna.tistory.com/32