[알고리즘] BFS (너비우선탐색) 구현해보기 (feat. TypeScript)

BFS에 대한 소개

BFS는 Breadh-First-Search의 약자로 너비우선탐색이라고 합니다.

그래프가 주어졌을 때, 노드(Vertex)를 가까운 노드부터 탐색하는 알고리즘입니다.

 

 

BFS 알고리즘을 구현할 때는 큐와 배열을 사용합니다.

큐는 현재 노드로부터 인접한 노드들을 담아주는 역할을 해줍니다.

배열은 현재 노드를 방문했는지 체크하는 역할로 사용됩니다.

 

가까운 노드(인접 노드)부터 탐색하기 때문에 A노드에서 B노드까지의 최단거리를 구할 수 있습니다.

 

 

DFS 알고리즘과 마찬가지로

그래프, 현재노드, 방문여부 정보를 넘겨줌으로써 알고리즘을 구현할 수 있습니다.

 

 

 

 

알고리즘

1. 시작 노드를 큐에 삽입합니다.

2. 방문하지 않았다면 방문했다고 체크합니다.

3. 큐에서 노드를 제거한 후, 해당 노드의 모든 인접 노드 중에서 방문하지 않은 노드들을 큐에 삽입하고 방문체크를 합니다.

4. 큐가 비어질 때까지 3을 반복합니다.

 

 

시간 복잡도

O(V+E)

노드 갯수 + 인접노드(간선 갯수)만큼 시간 복잡도가 발생합니다.

 

 

 

 

BFS 알고리즘을 하나씩 실행한 모습

012345678

 

 

 

BFS 구현 코드 (with TypeScript)

{
  function bfs(graph: number[][], v: number, visited) {
    const queue = [v];
    visited[v] = true;

    while (queue.length) {
      const v = queue.shift();
      console.log(v);

      for (const i of graph[v]) {
        if (!visited[i]) {
          queue.push(i);
          visited[i] = true;
        }
      }
    }
  }

  const graph = [[], [2, 3, 4], [1, 5], [1, 6, 7], [1], [2], [3, 7], [3, 6]];
  const visited = new Array(graph.length).fill(false);

  // 시작 노드를 4부터 시작
  bfs(graph, 4, visited);
}

 

출력결과

4 -> 1 -> 2 -> 3 -> 5 -> 6 -> 7

 

 

 

 

 

BFS 알고리즘을 하나씩 실행한 모습 (최단거리 표시)

01234567

 

 

BFS 구현 코드 (최단거리)

{
  function bfs_shortest_path(
    graph: number[][],
    v: number,
    visited,
    pathLengths: number[]
  ) {
    const queue = [v];
    visited[v] = true;

    while (queue.length) {
      const v = queue.shift();
      // console.log(v);

      for (const i of graph[v]) {
        if (!visited[i]) {
          queue.push(i);
          visited[i] = true;
          pathLengths[i] = pathLengths[v] + 1;
        }
      }
    }
  }

  const graph = [[], [2, 3, 4], [1, 5], [1, 6, 7], [1], [2], [3, 7], [3, 6]];
  const visited = new Array(graph.length).fill(false);
  const pathLengths = new Array(graph.length).fill(0);

  bfs_shortest_path(graph, 4, visited, pathLengths);
  
  // 4번 노드로부터의 최단거리 출력
  console.log(pathLengths);
}

 

출력결과

[ 0, 1, 2, 2, 0, 3, 3, 3 ]