BFS

BFS란?

BFS 는 동일 깊이의 가까운 정점들을 차례로 탐색한 뒤, 그 다음 깊이로 내려가 탐색하는 방식

특징

• queue 가 사용된다
• 최단거리 문제(가중치가 없는, 가중치가 1인)에서 BFS 가 사용된다

구현

• 입력으로 아래와 같이 주어질 때
  

7
6
1 2
2 3
1 5
5 2
5 6
4 7

public static void bfs(int[][] graph, boolean[] visited, int start) {
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(start);
    visited[start] = true; // 시작 정점을 방문했다고 표시

    while (!queue.isEmpty()) {
      int vertex = queue.poll();

      // 현재 정점과 인접한 모든 정점을 확인
      for (int i = 1; i < graph.length; i++) {
        // 인접하고 아직 방문하지 않은 정점이 있다면
        if (graph[vertex][i] == 1 && !visited[i]) {
          visited[i] = true; // 해당 정점을 방문했다고 표시
          queue.offer(i); // 큐에 추가
        }
      }
    }
  }