【TypeScriptで学ぶアルゴリズム】幅優先探索(BFS)

幅優先探索

同じレベル（階層）にあるノード（隣接ノード）を先に探索してから、次のレベルのノードを探索する手法です。

木構造の上部（上レイヤー）から少しづつ巡回していくイメージです。

幅優先探索の実装例

1. グラフを表すデータの型定義

BFS.ts

//グラフの隣接リストを表す型
type Graph = { [key: string]: string[] };

グラフデータの定義

BFS.ts

const graph: Graph = {
  'A': ['B', 'C'],
  'B': ['D', 'E'],
  'C': ['F'],
  'D': [],
  'E': ['F'],
  'F': []
};

2. DFSの実装

BFS.ts

function bfs(graph: Graph, start: string): string[] {
  const visited: Set<string> = new Set();
  const queue: string[] = [start];
  const result: string[] = [];

  while (queue.length > 0) {
    const node = queue.shift();
    
    if (node && !visited.has(node)) {
      visited.add(node);
      result.push(node);

      //次のレベルのノードをキューに追加
      queue.push(...graph[node]);
    }
  }

  return result;
}

const result = bfs(graph, 'A');
console.log(result); 

//出力は以下!
//['A', 'B', 'C', 'D', 'E', 'F']

以下は同じデータを深さ優先探索した記事です。