グラフィックで説明する 10 個のグラフアルゴリズム

例と視覚化による 10 個の基本的なグラフアルゴリズムの簡単な紹介

グラフは、ソーシャルメディアネットワーク、Web ページやリンク、GPS の位置やルートなど、現実世界のデータをモデル化およびキャプチャするための強力な手段となっています。相互に関連するオブジェクトのセットがある場合は、グラフを使用してそれらを表現できます。

> 著者による画像

この記事では、分析に非常に役立つ 10 個の基本的なグラフアルゴリズムとその応用について簡単に説明します。

まずはチャートをご紹介しましょう。

グラフとは何ですか?

グラフは、頂点またはノードの有限の集合と、それらの頂点を接続するエッジの集合で構成されます。 2 つの頂点が同じ辺で互いに接続されている場合、それらは隣接頂点と呼ばれます。

以下はグラフに関連する基本的な定義です。例については図 1 を参照してください。

順序: グラフの頂点の数
サイズ: グラフのエッジの数
頂点次数: 頂点に接続する辺の数
孤立頂点: グラフ内の他のどの頂点とも接続されていない頂点
自己ループ: 頂点からそれ自身への辺
有向グラフ: すべての辺に方向があり、どの頂点が開始頂点でどの頂点が終了頂点であるかを示すグラフ
無向グラフ: 方向を持たない辺を持つグラフ
重み付きグラフ: グラフのエッジには重みがあります
重みなしグラフ: グラフのエッジには重みがありません

> 図1. グラフ用語の視覚化（著者撮影）

1. 幅優先探索

> 図 2. グラフの BFS トラバーサルのアニメーション (画像提供: 著者)

トラバーサルまたは検索は、グラフ上で実行できる基本的な操作の 1 つです。幅優先探索 (BFS) では、特定の頂点から開始し、現在の深さでそのすべての隣接頂点を探索してから、次のレベルの頂点に進みます。ツリーとは異なり、グラフにはサイクル (最初の頂点と最後の頂点が同じであるパス) を含めることができます。したがって、訪問した頂点を追跡する必要があります。 BFS を実装する際には、キューデータ構造を使用します。

図 2 は、サンプルグラフの BFS トラバーサルのアニメーションを示しています。頂点がどのように発見され (黄色)、訪問されるか (赤) に注目してください。

応用分野

最短経路と最小全域木を決定するために使用されます。
検索エンジンのクローラーは、Web ページのインデックスを構築するために使用されます。
ソーシャルネットワークで検索するために使用されます。
BitTorrent などのピアツーピアネットワークで利用可能な隣接ノードを検索するために使用されます。

2. 深さ優先探索

> 図3. グラフのDFSトラバーサルのアニメーション（画像提供：著者）

深さ優先探索 (DFS) では、特定の頂点から開始し、バックトラック (バックトラッキング) する前に各ブランチに沿って可能な限り探索します。 DFS では、訪問した頂点も追跡する必要があります。 DFS を実装する場合、バックトラックをサポートするためにスタックデータ構造を使用します。

図３は、図２と同じグラフ例のDFSトラバーサルのアニメーションを示す。深さを横断してバックトラックする方法に注目してください。

応用分野

2 つの頂点間のパスを見つけるために使用されます。
グラフ内のサイクルを検出するのに役立ちます。
トポロジカルソートに使用されます。
迷路など、答えが 1 つしかないパズルを解くときに使用します。

3. 最短経路

> 図4. 頂点1から頂点6までの最短経路を示すアニメーション（画像提供：著者）

ある頂点から別の頂点までの最短経路は、移動する必要があるエッジの重みの合計が最小になるようなグラフ内の経路です。

図 4 は、グラフ内の頂点 1 から頂点 6 までの最短経路を決定するアニメーションを示しています。

アルゴリズム

ダイクストラ最短経路アルゴリズム
ベルマン・フォードアルゴリズム

応用分野

Google マップや Apple マップなどのマッピングソフトウェアで、ある場所から別の場所への道順を検索するために使用されます。
最小遅延パス問題を解決するためにネットワークで使用されます。
抽象マシンで、異なる状態間を遷移することで何らかの目標状態に到達するためのオプションを決定するために使用されます (たとえば、ゲームに勝つための最小限の移動数を決定するために使用できます)。

[[345972]]

> Daniel Dino-SloferによるPixabayの画像

4. サイクル検出

> 図5. サイクル（著者撮影）

サイクルとは、グラフ内の最初の頂点と最後の頂点が同じであるパスです。頂点から開始し、パスをたどり、開始頂点で終了する場合、このパスは循環になります。サイクル検出は、これらのサイクルを検出するプロセスです。図 5 はループを移動するアニメーションを示しています。

アルゴリズム

フロイドサイクル検出アルゴリズム
ブレントアルゴリズム

応用分野

分散メッセージベースのアルゴリズム用。
クラスター上の分散処理システムを使用して大規模なグラフを処理するために使用されます。
並行システムでデッドロックを検出するために使用されます。
暗号化アプリケーションで、同じ暗号化値にマップされるメッセージを決定するために使用されるキー。

5. 最小全域木

> 図 6. 最小全域木を示すアニメーション (画像提供: 著者)

最小全域木は、すべての頂点を最小の辺の重みの合計で接続し、サイクルを含まないグラフの辺のサブセットです。

図 6 は、最小全域木を取得するプロセスを示すアニメーションです。

アルゴリズム

プリムのアルゴリズム
クラスカルのアルゴリズム

応用分野

コンピュータネットワークでブロードキャストするためのツリーを構築するために使用されます。
グラフベースのクラスター分析に使用されます。
画像のセグメンテーションに使用されます。
社会地域を連続した地域に分割するために使用される社会地理領域の地域化。

6. 強く連結されたコンポーネント

> 図 7. 強く連結されたコンポーネント (画像提供: 著者)

グラフ内のすべての頂点が他のすべての頂点から到達可能である場合、そのグラフは強く接続されていると言われます。

図 7 は、頂点が赤、緑、黄色の 3 つの強く接続されたコンポーネントを含むグラフの例を示しています。

アルゴリズム

コサラジュのアルゴリズム
Tarjan の強連結成分アルゴリズム

応用分野

二部グラフのエッジの分類であるダルメージ・メンデルゾーン分解を計算するために使用されます。
ソーシャルネットワークで、密接に関係する人々のグループを見つけ、共通の関心に基づいて推奨を行うために使用されます。

[[345975]]

> Gerd AltmannによるPixabayの画像

7. トポロジカルソート

> 図8. グラフの頂点の位相的順序（著者撮影）

グラフの位相的順序付けは、その頂点の線形順序付けであり、順序付け内のあらゆる有向辺 (u, v) について、頂点 u が v の前に来ます。

図 8 は、頂点の位相順序 (1、2、3、5、4、6、7、8) の例を示しています。頂点 5 は頂点 2 と 3 の後に来る必要があることがわかります。同様に、頂点 6 は頂点 4 と 5 の後に配置する必要があります。

アルゴリズム

カーンアルゴリズム
深さ優先探索アルゴリズム

応用分野

命令のスケジュールに使用されます。
データのシリアル化に使用されます。
メイクファイル内でコンパイルタスクが実行される順序を決定するために使用されます。
リンカー内のシンボル依存関係を解決するために使用されます。

8. グラフィックの色付け

> 図9. 頂点カラーリング（著者撮影）

グラフの色付けは、特定の条件を確保しながらグラフ要素に色を割り当てます。頂点シェーディングは、最も一般的に使用されるグラフィックシェーディング手法です。頂点彩色では、k 色を使用してグラフの頂点を彩色しようとしますが、隣接する 2 つの頂点は同じ色であってはなりません。その他のシェーディング手法には、エッジシェーディングやフェイスシェーディングなどがあります。

グラフの彩度数とは、グラフを色付けするために必要な最小の色数です。

図 9 は、4 色を使用してサンプルグラフの頂点を色付けした様子を示しています。

アルゴリズム