Rubyで学ぶ実践グラフ理論：基礎からアルゴリズム活用まで

本記事は「実践コンピュータサイエンス」シリーズの続編です。古典的なコンピュータサイエンスの概念を、Rubyを使って実際の問題解決に応用する方法を学んでいきます。

今回のテーマはグラフ理論です。

二分木（バイナリツリー）という言葉を耳にしたことがある方も多いでしょう。二分木は次のような構造をしています。

実は、二分木とはグラフの特殊な一種にすぎません。このことからも、グラフがいかに広く普及したデータ構造であるかがわかります。

まずはグラフ理論の基礎を概観し、その後、実用的な活用例とRubyでの実装方法を見ていきましょう。

グラフの基本

グラフは次の2つの要素で構成されます。

• ノード（頂点とも呼ばれます）
• エッジ（辺）

ノードはグラフ内の一つの要素を表します。例えば地図をグラフで表現する場合、都市や道路がノードに相当します。一方、エッジはノード同士をつなぐ接続関係を表します。

コンピュータサイエンスや数学の教科書では、グラフは次の式で定義されています。G(V, E)

ここでGはグラフ、Vは頂点の集合、Eはエッジの集合を意味します。

グラフには「有向グラフ」と「無向グラフ」の2種類があります。有向グラフでは一方向にしか移動できず、無向グラフでは双方向の移動が可能です。

最もよく知られているグラフの種類はDAG（有向非巡回グラフ：Directed Acyclic Graph）です。「非巡回（Acyclic）」とはループが存在しない、つまり来た道を引き返す経路がないことを意味します。

グラフの活用例

基礎を理解したところで、グラフの代表的な活用例を見てみましょう。

グラフを使うことで、次のようなことが可能になります。

• 2つの地点間の最短経路（または最長経路）の探索
• 2つの要素間に関係性があるかどうかの判定
• レコメンデーションエンジンの構築
• 依存関係の分析

その他の例としては、目的地までの最適ルートの検索（GPSナビゲーションなど）が挙げられます。

Rubyでのグラフの実装と使い方

独自にグラフを実装することもできますが、本記事では既存の実装を提供してくれる「RGL」gemを使用します。

RGLを使って基本的なグラフを作成するコードは以下の通りです。

require 'rgl/adjacency'

graph = RGL::DirectedAdjacencyGraph.new

graph.add_edge 1,2
graph.add_edge 3,4
graph.add_edge 1,4
graph.add_edge 4,3

このコードを実行すると、次のようなグラフが生成されます。

作成したグラフを視覚的に確認したい場合は、以下のようにします。

require 'rgl/dot'

graph.print_dotted_on

このメソッドの出力結果をコピーして、dot言語を処理できるサイトに貼り付ければ、グラフを画像として表示できます。

あるいは、Graphvizをローカル環境にインストールして、自分のマシン上で画像を生成することも可能です。

グラフが用意できたら、次はそれを走査（トラバース）して情報を取得したくなりますよね。

グラフ探索には2つの基本的なアルゴリズムがあります。

• 幅優先探索（BFS：Breadth-First Search）
• 深さ優先探索（DFS：Depth-First Search）

BFSでは開始点に近いノードから順に訪問し、DFSでは各ノードについて可能な限り深く潜っていきます。これらのアルゴリズムはスタックというデータ構造を使って実装できます。

幸い、RGL gemにはこれらのアルゴリズムがすでに実装されています。

require 'rgl/traversal'

graph.bfs_iterator.to_a
# [1, 2, 4, 3]

graph.dfs_iterator.to_a
# [1, 4, 3, 2]

先ほどのグラフをもう一度見て、これらのアルゴリズムがたどった経路を目で追ってみてください（指を使ってもOKです）。動作のイメージがつかみやすくなるでしょう。

重み付きグラフ

グラフに「重み」という形で追加情報を持たせると、より実用的になります。

重みはエッジ、つまり2つのノード（頂点）をつなぐ経路に対して与えられます。この重みは、ある地点から別の地点へ移動するコストを表します。

例えば、ある国の地図をグラフとして表現し、目的地へできるだけ短時間で到達したい場合、重みは2つの都市間の距離を表すことになります。

また、コンピュータネットワークの場合、重みは特定のネットワークに到達するまでのホップ数を表すこともあります。

「コンピュータネットワークにおけるホップとは、送信元から宛先への経路の一部分を指します。データパケットは送信元から宛先へ移動する過程で、ブリッジ、ルーター、ゲートウェイを通過します。パケットが次のネットワーク機器に渡されるたびに、1ホップが発生します。」 – Wikipediaより

以下は重み付きグラフのコード例です。

graph = RGL::DirectedAdjacencyGraph.new
graph.add_vertices "Los Angeles", "New York", "Chicago", "Houston", "Seattle"

edge_weights =
{
  ["New York", "Los Angeles"] => 2445,
  ["Los Angeles", "Chicago"] => 2015,
  ["Los Angeles", "Houston"] => 1547,
  ["Chicago", "Houston"] => 939,
  ["Seattle", "Los Angeles"] => 1548
}

edge_weights.each { |(city1, city2), w| graph.add_edge(city1, city2) }

これである地点から別の地点への最短経路を検索できるようになりました。そして、まさにそれこそが次のセクションのテーマです！

最短経路の探索

グラフ内の最短経路を求める有名なアルゴリズムの一つが、「ダイクストラ法（Dijkstra's Shortest Path）」です。

重み付きグラフが与えられたとき、ダイクストラ法を使えば次の問いに答えることができます。

「A地点からB地点へ最速で移動するには、どのルートを選べばよいか？」

RGL gemを使ったコード例がこちらです。

p graph.dijkstra_shortest_path(edge_weights, "New York", "Houston")
# ["New York", "Los Angeles", "Houston"]

この結果から、グラフ内の情報をもとに、ニューヨークからヒューストンへの最短経路がわかります。

まとめ

本記事では、グラフというデータ構造が何であるか、そしてRGL gemを使ってどのように扱うかを学びました。

さらに、DFS、BFS、ダイクストラ法といった、グラフを操作するための主要なアルゴリズムについても理解を深めることができました。

本記事が役に立ったと思ったら、ぜひシェアしてください。より多くの人に届きますように 🙂