[알고리즘] BFS

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

 

특징

- 루트노드에서 시작하여 인접한 노드를 먼저 탐색하는 방법

- 가까운 정점을 먼저 방문, 멀리 떨어져 있는 정점을 나중에 방문하는 방식

 

사용되는 상황

- 두 노드 사이의 최단 경로 / 임의의 경로를 찾고 싶을 때 해당 알고리즘을 사용

 

알고리즘 특징

- 어떤 노드를 방문했었는지 여부를 반드시 검사
- 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 Queue를 사용

 

구현 (Javascript)

const graph = {
  A: ["B", "C"],
  B: ["A", "D"],
  C: ["A", "G", "H", "I"],
  D: ["B", "E", "F"],
  E: ["D"],
  F: ["D"],
  G: ["C"],
  H: ["C"],
  I: ["C", "J"],
  J: ["I"]
};

const DFS = (graph, startNode) => {
  const visited = []; // 탐색을 마친 노드들
  let needVisit = []; // 탐색해야할 노드들

  needVisit.push(startNode); // 노드 탐색 시작

  while (needVisit.length !== 0) { // 탐색해야할 노드가 남아있다면
    const node = needVisit.shift(); // queue이기 때문에 선입선출, shift()를 사용한다.
    if (!visited.includes(node)) { // 해당 노드가 탐색된 적 없다면
      visited.push(node); 
      needVisit = [...graph[node], ...needVisit];
    }
  }
  return visited;
};

console.log(DFS(graph, "A"));
// ["A", "B", "D", "E", "F", "C", "G", "H", "I", "J"]

 

 

구현 (Java) - 2차원 배열 활용

import java.util.*;

class Main {
  static int n, m, v;
  static int connect[][]; // 서로 연결되어 있는 정점인지 확인
  static boolean visited[]; // 방문한 정점인지 확인

  public static void BFS(){
    Queue<Integer> queue = new LinkedList<Integer>(); // 방문하는 정점을 Queue에 저장
    queue.offer(v); //시작점도 Queue에 넣어야 함
    visited[v] = true; // 방문하였다고 체크
    System.out.print(v + " ");
    
    while(!queue.isEmpty()) { // Queue가 빌때까지 반복
      int q = queue.poll(); // Queue에 맨 앞 요소 제거
      
      for(int j = 1; j <= n; j++) { // 전체 정점의 개수 만큼 반복 
        if(connect[q][j] == 1 && visited[j] == false) { // 방금 Queue에서 제거한 요소와 연결 되어있고, 아직 방문하지 않은 정점 찾기
          queue.offer(j); // 해당 요소를 Queue에 삽입
          visited[j] = true; // 방문하였다고 체크
          System.out.print(j + " ");
        }
      }
    }
  }
  
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    connect = new int[1001][1001]; 
    visited = new boolean[1001]; 

    n = sc.nextInt();
    m = sc.nextInt();
    v = sc.nextInt();
    
    for(int i = 0; i < m; i++){
      int x = sc.nextInt();
      int y = sc.nextInt();

      connect[x][y] = connect[y][x] = 1; // 서로의 정점을 연결
    }
    
    BFS();
  }
}

 

 

구현(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();
  }

  void addEdge(int v, int w) { 
    adj[v].add(w); // 인접 리스트에서 서로의 노드를 연결
  }


  void BFS(int s) {   
    boolean visited[] = new boolean[V]; // 방문하였는지 체크
    LinkedList<Integer> queue = new LinkedList<Integer>(); // Queue 생성

    visited[s] = true;
    queue.add(s); // 시작 노드를 queue에 삽입

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

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

public static void main(String args[]) {
  Graph g = new Graph(4); // 정점의 개수 만큼 Graph 생성

  // 서로의 정점을 연결
  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 탐색 
}

 

 

Reference

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