1 つの記事で 10 個のアルゴリズムをカバーします。基本的なグラフアルゴリズムの視覚的な説明

[[343053]]

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

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

まず、チャートとは何でしょうか?

グラフは、頂点またはノードの有限集合と、これらの頂点を接続する辺の集合で構成されます。 2 つの頂点が同じ辺で互いに接続されている場合、それらは隣接していると言われます。以下にチャートに関する基本的な定義を示します。図の例も参照してください。

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

図1: グラフ用語の視覚化

1. 幅優先探索

図2: 幅優先探索(BFS)のトラバーサルアニメーション

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

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

応用：

• ソーシャルネットワーク検索
• 最短経路と最小全域木を決定するために使用される
• 検索エンジンのクローラーがウェブページのインデックスを作成するために使用します
• BitTorrentなどのピアツーピアネットワークで利用可能な近隣ノードを見つけるために使用される

2. 深さ優先探索

図3: 深さ優先探索(DFS)の走査のアニメーション

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

図 3 は、図 2 で使用したのと同じサンプル グラフの DFS トラバーサルのアニメーションです。深度までトラバースしてバックトラックする方法を示しています。

応用：

• 2つの頂点間の経路を見つけるために使用します
• グラフのサイクルを検出するために使用
• トポロジカルソートの場合
• 迷路など、答えが1つしかないパズルを解くのに使用します。

3. 最短経路

図4のアニメーションは頂点1から頂点6までの最短経路を示しています。

ある頂点から別の頂点までの最短経路は、移動するエッジの重みの合計が最小になるグラフ内の経路です。図 4 は、グラフ内の頂点 1 から頂点 6 までの最短経路を決定するアニメーションを示しています。

アルゴリズム：

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

応用：

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

4. サイクル検出

図5: ループ

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

アルゴリズム：

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

応用：

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

5. 最小全域木

図6. 最小全域木を示すアニメーション

最小全域木は、すべての頂点を最小のエッジ重みの合計で接続し、サイクルを含まないグラフのエッジのサブセットです。図 6 は、最小全域木を取得するプロセスのアニメーションです。

アルゴリズム：

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

応用：

• コンピュータネットワークのブロードキャストツリーを構築するために使用される
• グラフベースのクラスター分析の場合
• 画像セグメンテーション
• 社会地理学の分野で地域区分を行うために使用され、地域を隣接するエリアに分割します。

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

図7: 強く連結されたコンポーネント

グラフ内のすべての頂点が他のすべての頂点を経由して到達できる場合、そのグラフは強く連結されています。図 7 には 3 つの強く接続されたコンポーネントが含まれており、頂点はそれぞれ赤、緑、黄色で表されます。

アルゴリズム：

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

応用：

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

7. トポロジカルソート

図8: グラフの頂点の位相的ソート

グラフのトポロジカルソートは、頂点の線形順序付けであり、順序付けにおけるすべての有向辺 (u, v) について、頂点 u が v の前に来ます。図 8 は、頂点 (1、2、3、5、4、6、7、8) のトポロジカルソートの例を示しています。ご覧のとおり、頂点 5 は頂点 2 と 3 の後に配置されます。同様に、頂点 6 は頂点 4 と 5 の後に配置する必要があります。

アルゴリズム：

• カーンアルゴリズム
• 深さ優先アルゴリズムに基づく

応用：

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

8. グラフの色付け

図9: 頂点シェーディング

グラフの色付けとは、特定の条件下でグラフの要素に色を割り当てることを指します。頂点の色付けは、最も一般的に使用されるグラフの色付け手法です。頂点彩色では、隣接する 2 つの頂点が同じ色にならないように、k 色を使用してグラフの頂点を彩色します。その他のシェーディング手法には、エッジ シェーディングやフェイス シェーディングなどがあります。グラフの彩度数とは、グラフを色付けするために必要な最小の色数です。図 9 は、頂点を 4 色でシェーディングした様子を示しています。

アルゴリズム：

• 幅優先探索や深さ優先探索を使用するアルゴリズム
• 貪欲な色付け

応用：

• タイムテーブルを作成するために使用
• 移動無線周波数の割り当て
• 数独パズルのモデリングと解決
• グラフが二部グラフであるかどうかを確認するために使用します
• 隣国や州の地図を異なる色で塗りつぶすのに使用します

9. 最大流量

図10: 最大流量の決定

グラフは、エッジの重みをフロー容量として持つフロー ネットワークとしてモデル化できます。最大流量問題では、最大流量を生み出す流路を見つける必要があります。図 10 は、ネットワークの最大フロー値と最終フロー値を決定するアニメーションの例です。

アルゴリズム：

• フォード・フルカーソンアルゴリズム
• エドモンズ・カープアルゴリズム
• ディニックアルゴリズム

応用：

• 航空会社のスケジュール管理や乗務員の手配に使用されます。
• 画像の背景と前景を見つけるための画像セグメンテーションに使用されます。
• 試合に勝てず、現在のチームの最強の選手と競争できない選手を排除するために使用されます。

10. マッチング

図11: 二部グラフマッチング

グラフ内のマッチングとは、共通の頂点を持たないエッジのセットです (つまり、2 つのエッジに共通の頂点はありません)。可能な限り多くの頂点と一致する最大数のエッジが含まれるマッチングは、最大マッチングと呼ばれます。図 11 は、それぞれオレンジ色と青色で表された 2 つの頂点セットを持つ二部グラフの完全マッチングを取得するアニメーションを示しています。

アルゴリズム：

• ホップクロフト・カープアルゴリズム
• ハンガリーアルゴリズム
• ブルーミングアルゴリズム

応用：

• 花嫁と花婿のマッチングに使用（結婚の安定性の問題）
• 頂点のカバレッジを決定する
• 交通理論において、旅行資源の割り当てと最適化の問題を解決するために使用される

これら 10 個の基本的なチャート アルゴリズムは広く使用されています。理解できましたか?

この記事はWeChatの公開アカウント「Reading the Core」から転載したもので、以下のQRコードからフォローできます。この記事を転載する場合は、Duxinshu の公開アカウントにご連絡ください。