Zenn
📖

グラフアルゴリズムの基礎を学ぶー概念と表現方法

2023/05/06に公開
algorithm
#
graph
tech

この記事は、グラフアルゴリズムシリーズの1番目の記事です。

  1. 概念と表現方法→現在地
  2. BFSとDFS
  3. UnionFind
  4. 最小全域木
  5. 単一始点最短経路問題
  6. 全点対最短経路問題（WIP）

最近の一ヶ月くらいはグラフについて学んでおり、ようやく一段落したところで、学びについてのまとめに、このシリーズの記事を執筆しました。グラフに関わるよく見られるアルゴリズムに入る前に、まずは基礎概念とコード上のグラフの表現方法について押さえておきたいところです。

概念

グラフは、オブジェクトやネットワークの関係性を表現する、我々の日常生活にかなり近いデータ構造の一つです。例えば、SNSサイトのフォロー・フォロワー関係はグラフーとして表現できます。

グラフを構成する単位として、

  • 頂点・ノード（vertex/node）、ネットワーク内の一つのオブジェクトを表す。この記事では、頂点とノードを同じ意味で使います。
  • エッジ・リンク（edge/link）、オブジェクトを連結する辺を表す。頂点に繋がっているエッジの数を**次数（degree）**と言います。この記事では、エッジとリンクを同じ意味で使います。

なお、エッジは単純に「繋がっていますよ」だけではなく、どのように繋がっているかを表現するために、重み・ウェイト（weight） をかけることや、方向（direction） を示すことができます。

ウェイトの性質によって、ウェイトあり（weighted graphs）・なしのグラフに分けられます。例えば、駅AからBまで1時間がかかる、という時の1時間がウェイトとして抽象化されることができます。具体的な繋がり方に関心がなければ、基本的にウェイトなしのグラフとなるでしょう。

同様に、方向の性質によって、有向図（directed graph） と無向図（undirected graph） に分けることができます。例えば、ウェブサイトのリンクの間の関係を考えると、無向図となるでしょう。また、フォローとフォロワー機能を考えると、一方的にファンとか、相互フォローしているとか、方向ありのグラフになります。方向ありの場合、次数はさらに入次数（in-degree）と出次数（out-degree）と分けられます。フォロー中とフォロワー数の数は、この出入の次数で表すことが可能でしょう。

より複雑な例を考えると、例えばGoogleマップ上の道路（エッジ）と交差点（頂点）が挙げられます。単純に道路の通行可能な状況を表すときに、方向なし、ウェイトなしで良いでしょう。距離・移動時間を表すために、ウェイトが必要になってきます。一方通行の道路か、対面通行の道路か、上り下りの交通量を区別するために、方向ありかつウェイトありのグラフになるでしょう。

このように、グラフは現実世界の多くの概念や現象を表現することに適している抽象概念となっています。ただ、データ構造の中でも割と複雑になっていて、前提知識としてハッシュセット、キュー、木、ヒープなど別のデータ構造も知らなければなりません。その関係もあって、グラフ系は一定のデータ構造の基礎知識を持ってからやったほうがスムーズになります。

グラフの表現

基本の概念はこれでわかったかと思いますが、グラフのデータを具体的に、コード上どう表現するのか、ここで触れておきたいと思います。

下記のグラフを例にします。

隣接リスト

よく見られるのは、隣接リスト（Adjacency List）との表現となります。

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

隣接リストでは、各ノードの隣接ノードをリストまたは集合で表現します。通常、連想配列（オブジェクト）やマップを使用して、ノードとそれに関連する隣接ノードのリストを保持します。隣接リストは、空間効率が高く、グラフにおけるエッジの数が比較的少ない場合に適しています（疎グラフ）。

なお、上記の例ではウェイトが表現できていませんが、必要な場合は、["A", "B"]とかを[[10, "A"], [5, "B"]]とかにすれば良いでしょう。

隣接行列

上記と類似して、隣接行列（Adjacency Matrix）もあります。

const nodes = ["A", "B", "C", "D", "E", "F"];
const adjacencyMatrix = [
  [0, 1, 1, 0, 0, 0], // A
  [1, 0, 0, 1, 1, 0], // B
  [1, 0, 0, 0, 0, 1], // C
  [0, 1, 0, 0, 0, 0], // D
  [0, 1, 0, 0, 0, 1], // E
  [0, 0, 1, 0, 1, 0], // F
];

隣接行列では、グラフのノード間のエッジの有無を二次元配列（行列）で表現します。行列のサイズは、ノード数×ノード数です。エッジが存在する場合、対応するセルに1（またはエッジのウェイト）を格納し、存在しない場合は0を格納します。隣接行列は、エッジの追加・削除やエッジの存在確認が高速に行えますが、空間効率が低いため、グラフが密である場合に適しています（密グラフ）。

エッジリスト

また、エッジだけを保存するエッジリスト（Edge List）もあります。

const edgeList = [
  ["A", "B"],
  ["A", "C"],
  ["B", "D"],
  ["B", "E"],
  ["C", "F"],
  ["E", "F"],
];

エッジリストでは、グラフのエッジをノードのペアのリストで表現します。各ペアは、連結された2つのノードを示します。エッジリストは、グラフのエッジのみを保持しているので、隣接リストや隣接行列と比較してシンプルな構造ですが、特定のノードの隣接ノードを取得する際に効率が低いとか、エッジ取得、追加、削除が遅いことが欠点です。ただ、疎グラフの場合空間効率が高いとか、ウェイト付きグラフは表現しやすい（要素を1つ追加するだけ）といったメリットもあります。

インシデントリスト

最後に、ノードとエッジ両方を保存する、インシデントリスト（Incidence List）の形式があります。

class Node {
  constructor(value) {
    this.value = value;
    this.edges = [];
  }
}

class Edge {
  constructor(node1, node2) {
    this.node1 = node1;
    this.node2 = node2;
  }
}

const A = new Node("A");
const B = new Node("B");
const C = new Node("C");
const D = new Node("D");
const E = new Node("E");
const F = new Node("F");

const edgeAB = new Edge(A, B);
const edgeAC = new Edge(A, C);
const edgeBD = new Edge(B, D);
const edgeBE = new Edge(B, E);
const edgeCF = new Edge(C, F);
const edgeEF = new Edge(E, F);

A.edges = [edgeAB, edgeAC];
B.edges = [edgeAB, edgeBD, edgeBE];
C.edges = [edgeAC, edgeCF];
D.edges = [edgeBD];
E.edges = [edgeBE, edgeEF];
F.edges = [edgeCF, edgeEF];

インシデントリストは、グラフのノードとエッジの両方を保持します。通常、オブジェクト（構造体とも）を使用してノードとエッジを表現し、ノードはエッジのリストへの参照を持ち、エッジは接続されたノードへの参照を持ちますので、おそらく一番理解しやすい表現かもしれません。ウェイトをつけたい場合はエッジクラスの定義を変えれば良いでしょう。

インシデントリストは、隣接リストと隣接行列の中間的な特性を持ち（空間効率やエッジの追加・削除といった意味で）、グラフの構造によっては効率的な表現方法になることがあります。もちろん、隣接ノードの取得が遅いとか、上記の表現より若干複雑になっているのも否めません。

表現の変換

上記のいくつかの表現方法を挙げましたが、場合によって相互変換するかもしれません。ただ別途の複雑度をもたらしているので、アルゴリズム全体の効率や実装の容易さとトレードオフして実際に判断する必要があります。

例えば、エッジリストと隣接リストの表現の間に次のように変換できます。

function edgeListToAdjList(edgeList) {
  const adjList = [];
  for (const [src, dst, weight] of edgeList) {
    adjList[src] = adjList[src] || [];
    adjList[src].push([dst, weight]);
    // 有向図の場合は以下の追加が不要
    adjList[dst] = adjList[dst] || [];
    adjList[dst].push([src, weight]);
  }
  return adjList;
}

function adjListToEdgeList(adjList) {
  const edgeList = [];
  for (let src = 0; src < adjList.length; src++) {
    for (const [dst, weight] of adjList[src]) {
      // 無向図の場合は重複防止のために必要、有向図の場合はif文不要
      if (src < dst) {
        edgeList.push([src, dst, weight]);
      }
    }
  }
  return edgeList;
}

運用場面

各表現をどのときに運用するか、こちらにまとめました。

表現方法 適している場面 良い点 悪い点
隣接リスト 疎グラフ、隣接ノードの取得やエッジの操作が高頻度 空間効率が高い、隣接ノードの取得が高速、エッジの操作が高速 エッジの存在確認が遅い
隣接行列 密グラフ、エッジの存在確認が高頻度 エッジの存在確認が高速、操作が単純 空間効率が低い、エッジの追加・削除が遅い
エッジリスト 疎グラフ、シンプルな表現が望ましい シンプル、空間効率が高い、重み付きグラフに対応 隣接ノードの取得が遅い、エッジの追加・削除が遅い、エッジの存在確認が遅い
インシデントリスト エッジの情報が重要、エッジの操作が高頻度 エッジの情報が直接的、空間効率が高い、エッジの操作が比較的高速 複雑な構造、隣接ノードの取得が遅い

中でも、隣接リストとエッジリストはよく使われます。自前にNodeやGraphクラスを構築する場合だと、インシデントリストの方が伝わりやすいでしょう。

終わりに

基礎概念と表現方法については一旦これで。次回はDFSとBFS探索について話します。

Discussion