너비 우선 탐색(Breadth-first search, BFS)

너비 우선 탐색이란?

• 시작 정점에서 인접한 모든 정점들을 우선 탐색하는 방법
• OPEN List(검색 가능성이 있는 노드의 집합)는 큐(Queue)를 사용해야지만 레벨 순서대로 접근 가능
• 출발노드에서 목표노드까지의 최단 길이 경로를 보장한다.
• 경로가 매우 길 경우, 탐색 가지가 급격히 증가하여 보다 많은 기억 공간이 필요하다.
• 탐색 지점에서 둥그렇게 탐색을 해나가는 느낌

설명

1. 방문을 체크하는 배열존재
2. 시작노드를 큐에 넣고 탐색시작
3. 이중 반복문을 사용!
   - 큐 안에 있는 값을 pop하고 pop해서 나온 값의 인접한 노드에 대해서 가져오고 방문한 적 없는 노드에 경우 방문체크해주고 큐안에 노드를 넣어준다.

예시

코드(Java)

import java.io.*;
import java.util.*;

/* 인접 리스트를 이용한 방향성 있는 그래프 클래스 */
class Graph {
  private int V; // 노드의 개수
  private LinkedList<Integer> adj[]; // 인접 리스트

  /** 생성자 */
  Graph(int v) {
    V = v;
    adj = new LinkedList[v];
    for (int i=0; i<v; ++i) // 인접 리스트 초기화
      adj[i] = new LinkedList();
  }

  /** 노드를 연결 v->w */
  void addEdge(int v, int w) { adj[v].add(w); }

  /** s를 시작 노드으로 한 BFS로 탐색하면서 탐색한 노드들을 출력 */
  void BFS(int s) {
    // 노드의 방문 여부 판단 (초깃값: false)
    boolean visited[] = new boolean[V];
    // BFS 구현을 위한 큐(Queue) 생성
    LinkedList<Integer> queue = new LinkedList<Integer>();

    // 현재 노드를 방문한 것으로 표시하고 큐에 삽입(enqueue)
    visited[s] = true;
    queue.add(s);

    // 큐(Queue)가 빌 때까지 반복
    while (queue.size() != 0) {
      // 방문한 노드를 큐에서 추출(dequeue)하고 값을 출력
      s = queue.poll();
      System.out.print(s + " ");

      // 방문한 노드와 인접한 모든 노드를 가져온다.
      Iterator<Integer> i = adj[s].listIterator();
      while (i.hasNext()) {
        int n = i.next();
        // 방문하지 않은 노드면 방문한 것으로 표시하고 큐에 삽입(enqueue)
        if (!visited[n]) {
          visited[n] = true;
          queue.add(n);
        }
      }
    }
  }
}

public static void main(String args[]) {
  Graph g = new Graph(4);

  g.addEdge(0, 1);
  g.addEdge(0, 2);
  g.addEdge(1, 2);
  g.addEdge(2, 0);
  g.addEdge(2, 3);
  g.addEdge(3, 3);

  g.BFS(2); /* 주어진 노드를 시작 노드로 BFS 탐색 */
}

References

https://ko.wikipedia.org/wiki/너비_우선_탐색

너비 우선 탐색 - 위키백과, 우리 모두의 백과사전

https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html

[알고리즘] 너비 우선 탐색(BFS)이란 - Heee's Development Blog