皆さんは「グラフ」という言葉を聞いて何を思い浮かべますか。Excel の折れ線グラフや棒グラフを想像する方が多いことでしょう。しかしアルゴリズムの文脈では、グラフは「モノとモノを繋ぐ関係」のことを指します。今回は、グラフの基本について整理した上で、どんな問題をグラフで表すことができるのかを紹介します。

グラフとは

グラフは、モノとモノを繋ぐ関係を表すネットワーク構造のようなものです。グラフは頂点と辺からなり、頂点はモノを、辺は繋がりを表します。イメージしづらい場合は、鉄道路線図の駅を頂点、線路を辺と考えると良いでしょう。なお、頂点同士を識別するため、各頂点には 1、2、3…… と番号が付けられることが多いです。

無向グラフと有向グラフ

下図左側のように、辺に向きが付いていないグラフを「無向グラフ」と言い、下図右側のように、辺に向きが付いているグラフを「有向グラフ」と言います。例えば、一方通行のある道路網は有向グラフで表すことが可能です。

重み付きグラフと重みなしグラフ

下図左側のように、辺に重み（長さなどの情報）が付いているグラフを「重み付きグラフ」と言い、下図右側のように、辺に重みが付いていないグラフを「重みなしグラフ」と言います。

例えば、鉄道路線図の駅間距離をグラフで表したい場合は、重み付きグラフを使う必要があります。なお、重みなしグラフは、全ての辺の重みが 1 であると見なすことも可能です。

グラフで表せる世の中の問題

各グラフの名称と概要は理解できましたか。グラフはとても応用範囲が広く、迷路から SNS まで、実社会のさまざまなモノをグラフで表すことができます。本稿では、グラフを使った代表的なアルゴリズム問題として 4 つの例題をご紹介します。

例 1：迷路の問題

マスを頂点とし、上下左右に隣り合う関係を辺とするとき、迷路は重みなし無向グラフとして表すことができます※。このグラフでは、「スタートからゴールまで最短何手で移動できますか？」といった最短経路を求める問題が考えられます。

※頂点番号の付け方に注意してください。

例 2：高速道路の路線図

インターチェンジ（IC）を頂点とし、道路を辺とするとき、高速道路は重み付き無向グラフとして表すことができます。ここで、辺の重みは移動時間を表します。このグラフでは、「東京 IC から名古屋 IC まで最短何分で移動できますか？」といった問題が考えられます。

例 3：SNS のフォロー関係

人を頂点とし、「誰が誰をフォローしているか」を辺とするとき、SNS のフォロー関係は重みなし有向グラフとして表すことができます。ただし、双方向の関係しか認めない SNS の場合、重みなし無向グラフとなります。このグラフでは、「最もフォロワーの多いユーザーは誰ですか？」といった問題が考えられます。

例 4：野球の試合結果

チームを頂点とし、「どのチームがどのチームに勝利したか」を辺とするとき、野球の試合結果は重みなし有向グラフとして表すことができます。ただし、得点差の情報もグラフに組み込みたいときは、重み付き有向グラフを使う必要があります。このグラフでは、「勝利数が最多のチームはどれですか？」といった問題が考えられます。

グラフの実装方法

最後に、グラフを Python で実装する方法について解説します。プログラムの書き方はさまざまですが、各頂点に対して「直接辺で結ばれている頂点」のリストを管理する「隣接リスト表現」を使うと、高速に動作することが多いです。

Python では、リスト型を用いて実装することができます。頂点 x に対する隣接リストを G[x] とするとき、頂点 a から頂点 b に向かう辺を追加する際は G[a].append(b) という操作を行えば良いです。なお、無向グラフの場合 append を 2 回行う必要がある点に注意が必要です。以下、実装例を示します。

# 隣接リストの定義
G = [[] for i in range(6)]

# 頂点 1-2 をつなぐ辺を追加
G[1].append(2)
G[2].append(1)

# 頂点 2-3 をつなぐ辺を追加
G[2].append(3)
G[3].append(2)

# 頂点 3-4 をつなぐ辺を追加
G[3].append(4)
G[4].append(3)

# 頂点 3-5 をつなぐ辺を追加
G[3].append(5)
G[5].append(3)

# 隣接リストの状態を出力
print(G[1]) # "[2]" と出力される
print(G[2]) # "[1, 3]" と出力される
print(G[3]) # "[2, 4, 5]" と出力される
print(G[4]) # "[3]" と出力される
print(G[5]) # "[3]" と出力される

＊　＊　＊

今回は、グラフの基本的な考え方をお伝えしました。実はグラフを使うと、深さ優先探索・幅優先探索・ダイクストラ法などのさまざまなアルゴリズムを実装することができ、解ける問題の幅が一気に広がります。次回以降は 3 回に分けて、グラフを使ったアルゴリズムを解説していきますので、楽しみにお待ちください。