グラフアルゴリズム

グラフアルゴリズムとは

グラフアルゴリズムは、ノード (頂点) とエッジ (辺) で構成されるグラフ構造に対する探索、最短経路、接続性の分析を行うアルゴリズムである。SNS のフォロー関係、ネットワークのルーティング、依存関係の解析で使われる。

グラフの種類

グラフの種類を以下にまとめる。

種類	説明	例
無向グラフ	エッジに方向がない	SNS の友達関係
有向グラフ	エッジに方向がある	フォロー関係、依存関係
重み付きグラフ	エッジにコスト (重み) がある	地図の距離
DAG (有向非巡回)	循環がない有向グラフ	ビルドの依存関係

探索アルゴリズム

探索アルゴリズムのコード例を示す。

// BFS (幅優先探索): 最短経路の発見
function bfs(graph: Map<string, string[]>, start: string): string[] {
  const visited = new Set<string>();
  const queue = [start];
  const result: string[] = [];
  while (queue.length > 0) {
    const node = queue.shift()!;
    if (visited.has(node)) continue;
    visited.add(node);
    result.push(node);
    queue.push(...(graph.get(node) || []));
  }
  return result;
}

// DFS (深さ優先探索): 経路の探索、トポロジカルソート
function dfs(graph: Map<string, string[]>, start: string, visited = new Set<string>()): string[] {
  if (visited.has(start)) return [];
  visited.add(start);
  const result = [start];
  for (const neighbor of graph.get(start) || []) {
    result.push(...dfs(graph, neighbor, visited));
  }
  return result;
}

BFS vs DFS

BFS と DFS の違いを以下にまとめる。

観点	BFS	DFS
データ構造	キュー	スタック (再帰)
最短経路	辺の重みが等しいグラフなら最短経路が得られる	先に見つかった経路が最短とは限らない
メモリ	多い (幅が広い場合)	少ない
用途	最短経路、レベル探索	経路探索、トポロジカルソート

トポロジカルソート

DAG のノードを依存関係の順序に並べる。ビルドシステム (Turborepo, Nx) で使われる。

依存関係: A → B, A → C, B → D, C → D  (矢印は「左が右に依存する」)
トポロジカルソート: A, B, C, D (or A, C, B, D)
ビルド順序: トポロジカル順の逆 = D → B, C (並列) → A

実務での利用

実務での利用を以下にまとめる。

場面	アルゴリズム
npm の依存解決	トポロジカルソート
ネットワークルーティング	ダイクストラ (最短経路)
SNS のフォロー推薦	BFS (共通の友達)
循環依存の検出	DFS (バックエッジの検出)
マイクロサービスの依存分析	DAG の可視化

Neptune (AWS のグラフ DB)

大規模なグラフデータ (SNS、不正検知) には Amazon Neptune を使う。クエリ言語はデータモデルで分かれ、プロパティグラフとして持つなら Gremlin または openCypher、RDF として持つなら SPARQL を使う (2026 年 8 月時点)。どのモデルで格納するかでクエリの書き方が変わるため、設計の最初に決める。

グラフアルゴリズムの関連書籍も参考になる。