グラフアルゴリズム

グラフアルゴリズムとは

グラフアルゴリズムは、ノード (頂点) とエッジ (辺) で構成されるグラフ構造に対する探索、最短経路、接続性の分析を行うアルゴリズムである。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 または SPARQL でクエリする。

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