JavaScriptで連結成分を抽出する方法 ― 定義された辺から移動可能な数値のセットを見つける

はじめに：問題の概要

次のような入力配列と、そこから得たい出力配列を考えてみましょう。

const input = ["0:3", "1:3", "4:5", "5:6", "6:8"];
const output = [
  [0, 1, 3],
  [4, 5, 6, 8]
];

ここでは、各数値をグラフの「ノード（頂点）」、ペア x:y をノードxとノードyをつなぐ「辺（エッジ）」とみなします。そのうえで、定義された辺をたどって互いに移動できる数値の集合を見つけることが求められます。

グラフ理論の用語で表現すると、これは連結成分を見つける問題です。たとえば上記の例では、4から0へはどの辺を使っても移動できないため、両者は異なるグループに属します。一方、1から0へは「3」を経由することで移動できるため、同じグループに含まれます。

つまり求める出力とは、ランダムに入力されうる数値の集合をもとに、相互に行き来できるノード同士をグループ化したものです。以下では、与えられた入力からこのような出力を構築するJavaScript関数を実装していきます。

実装例

const input = ["0:3", "1:3", "4:5", "5:6", "6:8"];

const groupRange = (arr = []) => {
  // 各ペアを分割して数値化し、昇順に並べ替える
  const edges = arr
    .map(el => el.split(':').map(Number).sort((a, b) => a - b))
    .sort((a, b) => a[0] - b[0]);

  const res = [[]];   // 最終的なグループを格納する配列
  const maxVal = [0]; // 各グループの現在の最大値
  let count = 0;

  edges.forEach(el => {
    if (el[0] > maxVal[maxVal.length - 1]) {
      // 既存のどのグループにもつながらない → 新しいグループを作成
      res.push(el);
      maxVal.push(el[1]);
      count++;
    } else {
      // 現在のグループにつながっている → マージして最大値を更新
      res[count] = res[count].concat(el);
      maxVal[maxVal.length - 1] = Math.max(maxVal[maxVal.length - 1], el[1]);
    }
  });

  return res.map(el => [...new Set(el)].sort((a, b) => a - b));
};

console.log(groupRange(input));

実行結果

コンソールには次のように表示されます。

[ [ 0, 1, 3 ], [ 4, 5, 6, 8 ] ]

アルゴリズムの流れ

1. 前処理：各要素を「:」で分割し、文字列ではなく数値として扱えるよう変換します。そのうえで、ペア内部・ペア同士をそれぞれ昇順に並べ替えておきます。
2. グルーピング：res が出力用のグループ配列、maxVal は「処理中のグループに含まれる最大値」を追跡する配列です。
3. 分岐判定：各辺の始点が現在の最大値より大きければ、既存のグループにはつながらない新しい領域なので、新グループを作成します。そうでなければ現在のグループに統合し、必要に応じて最大値を更新します。
4. 後処理：各グループから重複を取り除き（Set）、昇順に並べ替えた配列を返します。

入力をあらかじめソートしておけば、あとは先頭から一度走査するだけでよいため、非常にシンプルかつ効率的な処理になります。なお、文字列のまま比較すると桁数の異なる数値が混在した場合に誤動作するおそれがあるため、Number で明示的に数値へ変換しておくことが重要です。

また、この手法は「辺が連続した範囲をつなぐ」という前提のもとで成立するものです。より一般的な任意のグラフ構造を扱う場合は、Union-Find（素集合データ構造）や DFS・BFS を用いて連結成分を求めるのが定番のアプローチとなりますので、用途に応じて使い分けるとよいでしょう。