칸비

개발 찍어먹기

[알고리즘]-너비 우선 탐색(BFS, Breadth-First Search)

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

개념

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법이다. 사용하는 경우 : 두 노드 사이의 최단 경로, 임의의 경로를 찾고 싶을 때

bfs가 dfs보다 복잡하다.

특징

dfs와 같이 노드의 방문 여부를 검사해야한다. 무한루프에 빠질 수 있다. 다익스트라 알고리즘과 유사하다.

구현 방법

  1. 큐(Queue)

복잡도

DFS(정점의 수:N, 간선의 수:E)의 모든 간선을 조회한다

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

인접리스트

제목

인접리스트는 정점과 간선의 표현을 배열을 통해 나타낸 방법이다. 인접리스트는 필요 공간만 사용 - O(N+E)의 공간복잡도 배열 A의 인덱스 1부터 시작한다. 정점 1과 인접한 다른정점(2, 5)을 ‘A[1] 2 5’ 이렇게 표현한다

인접행렬

제목

인접행렬은 정점과 간선의 표현을 행렬로 나타낸 방법이다. 인접행렬은 그림처럼 인접해 있으면 1로 표현해주고 인접하지 않으면 0으로 표기한다. 인접행렬의 크기는 정점과 간선 갯수 상관없이 O(N^2)의 공간복잡도

인접행렬이 익숙하고 쉬운 편이지만 인접리스트가 공간적으로 효율적이다.

BFS 구현 코드 예시


public static void bfs(int start) {

    Queue queue = new LinkedList(); // 큐

    queue.offer(start); // 시작점
    visited[start] = true; // 방문 표시
    System.out.print(start + " ");

    while(!queue.isEmpty()) {

      int temp = queue.poll();

      for(int j = 1; j <= n; j++) {

        if(arr[temp][j] == 1 && !visited[j]) { // 이어져있고 방문 안한 곳

          queue.offer(j); // 큐에 넣고
          visited[j] = true; // 방문 표시
          System.out.print(j + " ");
        }
      }
    }
}

요약

  • 다익스트라 알고리즘에 BFS가 이용된다.
  • DFS는 가까운곳을 먼저 탐색한다.

참고