10日で覚えるData Structure & AlgorithmDay 9: グラフ
books.chapter 910日で覚えるData Structure & Algorithm

Day 9: グラフ

今日学ぶこと

  • グラフの基本概念と用語
  • グラフの表現方法（隣接リスト・隣接行列）
  • BFS（幅優先探索）とDFS（深さ優先探索）
  • ダイクストラ法による最短経路探索

グラフとは

グラフ（Graph） は、ノード（頂点）とそれらを結ぶエッジ（辺）からなるデータ構造です。木はグラフの一種です。

flowchart LR
    A["A"] --- B["B"]
    A --- C["C"]
    B --- D["D"]
    C --- D
    B --- E["E"]
    D --- E
    style A fill:#3b82f6,color:#fff
    style B fill:#8b5cf6,color:#fff
    style C fill:#22c55e,color:#fff
    style D fill:#f59e0b,color:#fff
    style E fill:#ef4444,color:#fff

用語

用語 説明
頂点（Vertex） グラフのノード
辺（Edge） 頂点間の接続
有向グラフ 辺に方向がある
無向グラフ 辺に方向がない
重み付きグラフ 辺にコスト（重み）がある
隣接（Adjacent） 辺で直接つながっている
次数（Degree） 頂点に接続する辺の数
経路（Path） 頂点の連続した列
サイクル（Cycle） 始点と終点が同じ経路

グラフの種類

flowchart TB
    subgraph Undirected["無向グラフ"]
        U1["A"] --- U2["B"]
        U2 --- U3["C"]
        U1 --- U3
    end
    subgraph Directed["有向グラフ"]
        D1["A"] --> D2["B"]
        D2 --> D3["C"]
        D3 --> D1
    end
    subgraph Weighted["重み付きグラフ"]
        W1["A"] -->|"5"| W2["B"]
        W2 -->|"3"| W3["C"]
        W1 -->|"10"| W3
    end
    style Undirected fill:#3b82f6,color:#fff
    style Directed fill:#8b5cf6,color:#fff
    style Weighted fill:#22c55e,color:#fff

グラフの表現方法

隣接リスト（Adjacency List）

各頂点の隣接する頂点をリストで保持します。疎なグラフに適しています。

class Graph {
  constructor() {
    this.adjacencyList = new Map();
  }

  addVertex(vertex) {
    if (!this.adjacencyList.has(vertex)) {
      this.adjacencyList.set(vertex, []);
    }
  }

  addEdge(v1, v2) {
    this.adjacencyList.get(v1).push(v2);
    this.adjacencyList.get(v2).push(v1); // Undirected
  }

  removeEdge(v1, v2) {
    this.adjacencyList.set(v1, this.adjacencyList.get(v1).filter(v => v !== v2));
    this.adjacencyList.set(v2, this.adjacencyList.get(v2).filter(v => v !== v1));
  }

  getNeighbors(vertex) {
    return this.adjacencyList.get(vertex) || [];
  }
}

const graph = new Graph();
["A", "B", "C", "D", "E"].forEach(v => graph.addVertex(v));
graph.addEdge("A", "B");
graph.addEdge("A", "C");
graph.addEdge("B", "D");
graph.addEdge("C", "D");
graph.addEdge("D", "E");

隣接行列（Adjacency Matrix）

2次元配列で辺の有無を表現します。密なグラフに適しています。

class GraphMatrix {
  constructor(size) {
    this.size = size;
    this.matrix = Array.from({ length: size }, () =>
      new Array(size).fill(0)
    );
    this.vertices = new Map(); // vertex name → index
  }

  addVertex(name) {
    const index = this.vertices.size;
    this.vertices.set(name, index);
  }

  addEdge(v1, v2, weight = 1) {
    const i = this.vertices.get(v1);
    const j = this.vertices.get(v2);
    this.matrix[i][j] = weight;
    this.matrix[j][i] = weight; // Undirected
  }

  hasEdge(v1, v2) {
    const i = this.vertices.get(v1);
    const j = this.vertices.get(v2);
    return this.matrix[i][j] !== 0;
  }
}

隣接リスト vs 隣接行列

特徴 隣接リスト 隣接行列
空間計算量 O(V + E) O(V²)
辺の存在確認 O(degree) O(1)
全辺の列挙 O(V + E) O(V²)
辺の追加 O(1) O(1)
適したグラフ 疎なグラフ 密なグラフ

BFS（幅優先探索）

BFSは、始点から近い順にノードを探索します。キューを使います。

flowchart LR
    subgraph BFS["BFS: A→B→C→D→E"]
        A["A\n(0)"] --> B["B\n(1)"]
        A --> C["C\n(1)"]
        B --> D["D\n(2)"]
        C -.-> D
        D --> E["E\n(3)"]
    end
    style A fill:#3b82f6,color:#fff
    style B fill:#8b5cf6,color:#fff
    style C fill:#8b5cf6,color:#fff
    style D fill:#22c55e,color:#fff
    style E fill:#f59e0b,color:#fff

function bfs(graph, start) {
  const visited = new Set();
  const queue = [start];
  const result = [];

  visited.add(start);

  while (queue.length > 0) {
    const vertex = queue.shift();
    result.push(vertex);

    for (const neighbor of graph.getNeighbors(vertex)) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
  return result;
}

console.log(bfs(graph, "A")); // ["A", "B", "C", "D", "E"]

BFSの最短経路

function shortestPath(graph, start, end) {
  const visited = new Set();
  const queue = [[start, [start]]];
  visited.add(start);

  while (queue.length > 0) {
    const [vertex, path] = queue.shift();

    if (vertex === end) return path;

    for (const neighbor of graph.getNeighbors(vertex)) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push([neighbor, [...path, neighbor]]);
      }
    }
  }
  return null; // No path found
}

console.log(shortestPath(graph, "A", "E")); // ["A", "B", "D", "E"]

DFS（深さ優先探索）

DFSは、行けるところまで深く探索し、行き詰まったら戻ります。スタック（または再帰）を使います。

// Recursive DFS
function dfs(graph, start, visited = new Set()) {
  visited.add(start);
  const result = [start];

  for (const neighbor of graph.getNeighbors(start)) {
    if (!visited.has(neighbor)) {
      result.push(...dfs(graph, neighbor, visited));
    }
  }
  return result;
}

// Iterative DFS
function dfsIterative(graph, start) {
  const visited = new Set();
  const stack = [start];
  const result = [];

  while (stack.length > 0) {
    const vertex = stack.pop();
    if (visited.has(vertex)) continue;

    visited.add(vertex);
    result.push(vertex);

    for (const neighbor of graph.getNeighbors(vertex)) {
      if (!visited.has(neighbor)) {
        stack.push(neighbor);
      }
    }
  }
  return result;
}

BFS vs DFS

特徴 BFS DFS
データ構造 キュー スタック/再帰
探索順序 近い順 深い順
最短経路 Yes No
空間計算量 O(V) O(V)
用途 最短経路、レベル探索 サイクル検出、トポロジカルソート

サイクル検出

function hasCycle(graph) {
  const visited = new Set();

  function dfs(vertex, parent) {
    visited.add(vertex);
    for (const neighbor of graph.getNeighbors(vertex)) {
      if (!visited.has(neighbor)) {
        if (dfs(neighbor, vertex)) return true;
      } else if (neighbor !== parent) {
        return true; // Cycle found
      }
    }
    return false;
  }

  for (const vertex of graph.adjacencyList.keys()) {
    if (!visited.has(vertex)) {
      if (dfs(vertex, null)) return true;
    }
  }
  return false;
}

ダイクストラ法（最短経路）

重み付きグラフで、始点から全頂点への最短経路を求めます。

flowchart LR
    A["A"] -->|"4"| B["B"]
    A -->|"2"| C["C"]
    B -->|"3"| D["D"]
    C -->|"1"| B
    C -->|"5"| D
    B -->|"1"| E["E"]
    D -->|"2"| E
    style A fill:#3b82f6,color:#fff
    style E fill:#22c55e,color:#fff

function dijkstra(graph, start) {
  const distances = new Map();
  const previous = new Map();
  const visited = new Set();

  // Initialize distances
  for (const vertex of graph.keys()) {
    distances.set(vertex, Infinity);
  }
  distances.set(start, 0);

  while (visited.size < graph.size) {
    // Find unvisited vertex with minimum distance
    let minVertex = null;
    let minDist = Infinity;
    for (const [vertex, dist] of distances) {
      if (!visited.has(vertex) && dist < minDist) {
        minVertex = vertex;
        minDist = dist;
      }
    }

    if (minVertex === null) break;
    visited.add(minVertex);

    // Update neighbors
    for (const { node, weight } of graph.get(minVertex)) {
      if (visited.has(node)) continue;
      const newDist = distances.get(minVertex) + weight;
      if (newDist < distances.get(node)) {
        distances.set(node, newDist);
        previous.set(node, minVertex);
      }
    }
  }

  return { distances, previous };
}

// Usage
const weightedGraph = new Map();
weightedGraph.set("A", [{ node: "B", weight: 4 }, { node: "C", weight: 2 }]);
weightedGraph.set("B", [{ node: "D", weight: 3 }, { node: "E", weight: 1 }]);
weightedGraph.set("C", [{ node: "B", weight: 1 }, { node: "D", weight: 5 }]);
weightedGraph.set("D", [{ node: "E", weight: 2 }]);
weightedGraph.set("E", []);

const result = dijkstra(weightedGraph, "A");
console.log(result.distances);
// Map { 'A' => 0, 'B' => 3, 'C' => 2, 'D' => 6, 'E' => 4 }

ダイクストラ法の計算量

実装 計算量
配列 O(V²)
優先度キュー O((V + E) log V)

トポロジカルソート

有向非巡回グラフ（DAG）の頂点を、辺の方向に沿って並べます。

function topologicalSort(graph) {
  const visited = new Set();
  const stack = [];

  function dfs(vertex) {
    visited.add(vertex);
    for (const neighbor of graph.get(vertex) || []) {
      if (!visited.has(neighbor)) {
        dfs(neighbor);
      }
    }
    stack.push(vertex);
  }

  for (const vertex of graph.keys()) {
    if (!visited.has(vertex)) {
      dfs(vertex);
    }
  }

  return stack.reverse();
}

// Task dependencies
const tasks = new Map();
tasks.set("A", ["C"]);
tasks.set("B", ["C", "D"]);
tasks.set("C", ["E"]);
tasks.set("D", ["E"]);
tasks.set("E", []);

console.log(topologicalSort(tasks));
// e.g., ["B", "D", "A", "C", "E"]

まとめ

概念 説明
グラフ 頂点と辺からなるデータ構造
BFS キューを使った近い順の探索
DFS スタック/再帰を使った深い順の探索
ダイクストラ法 重み付きグラフの最短経路アルゴリズム
トポロジカルソート DAGの依存関係順の並び替え

重要ポイント

  1. 隣接リストは疎なグラフ、隣接行列は密なグラフに適する
  2. BFSは最短経路を保証する（重みなしグラフ）
  3. DFSはサイクル検出やトポロジカルソートに適する
  4. ダイクストラ法は負の重みに対応できない（→ベルマンフォード法）

練習問題

問題1: 基本

無向グラフで2つの頂点間に経路が存在するかを判定する関数を実装してください。

問題2: 応用

無向グラフの連結成分（Connected Components）の数を求める関数を実装してください。

チャレンジ問題

重み付き有向グラフで、ダイクストラ法を優先度キューを使って実装し、始点から終点までの最短経路とそのコストを返してください。

参考リンク

次回予告: Day 10では「動的計画法と貪欲法」について学びます。最適化問題を解く2つの強力な手法を理解しましょう。