1 つの記事で 10 個のアルゴリズムをカバーします。基本的なグラフアルゴリズムの視覚的な説明
|
グラフは、ソーシャル メディア ネットワーク、Web ページやリンク、GPS の位置やルートなど、現実世界のシナリオでデータをモデル化およびキャプチャするための強力な手段となっています。一連のオブジェクトが相互に関連している場合、それらをグラフで表すことができます。 この記事では、分析と応用に非常に役立つ 10 個の基本的なチャート アルゴリズムについて簡単に説明します。 まず、チャートとは何でしょうか? グラフは、頂点またはノードの有限集合と、これらの頂点を接続する辺の集合で構成されます。 2 つの頂点が同じ辺で互いに接続されている場合、それらは隣接していると言われます。以下にチャートに関する基本的な定義を示します。図の例も参照してください。
図1: グラフ用語の視覚化 1. 幅優先探索 図2: 幅優先探索(BFS)のトラバーサルアニメーション トラバーサルまたは検索は、グラフ上で実行される基本的な操作の 1 つです。幅優先探索 (BFS) では、特定の頂点から開始して、次のレベルの頂点に進む前に、その頂点の現在の深さに関するすべての関連情報が探索されます。ツリーとは異なり、グラフにはサイクル (最初の頂点と最後の頂点が同じであるパス) を含めることができます。したがって、訪問した頂点を追跡する必要があります。 BFS を実装する場合は、キュー データ構造を使用する必要があります。 図 2 は、サンプル グラフの BFS トラバーサルのアニメーションです。頂点がどのように検出され (黄色)、訪問されるか (赤) に注目してください。 応用：
2. 深さ優先探索 図3: 深さ優先探索(DFS)の走査のアニメーション 深さ優先探索 (DFS) では、特定の頂点から開始し、バックトラックする前に各ブランチに沿って可能な限り探索します。 DFS では、訪問された頂点を追跡することも必要です。 DFS を実装する場合、バックトラックをサポートするためにスタック データ構造が使用されます。 図 3 は、図 2 で使用したのと同じサンプル グラフの DFS トラバーサルのアニメーションです。深度までトラバースしてバックトラックする方法を示しています。 応用：
3. 最短経路 図4のアニメーションは頂点1から頂点6までの最短経路を示しています。 ある頂点から別の頂点までの最短経路は、移動するエッジの重みの合計が最小になるグラフ内の経路です。図 4 は、グラフ内の頂点 1 から頂点 6 までの最短経路を決定するアニメーションを示しています。 アルゴリズム：
応用：
4. サイクル検出 図5: ループ サイクルとは、グラフ内の最初の頂点と最後の頂点が同じであるパスです。頂点から開始し、パスをたどって最終的に開始点に到達する場合、このパスは循環です。サイクル検出は、これらのサイクルを検出するプロセスです。図 5 はループを移動するアニメーションを示しています。 アルゴリズム：
応用：
5. 最小全域木 図6. 最小全域木を示すアニメーション 最小全域木は、すべての頂点を最小のエッジ重みの合計で接続し、サイクルを含まないグラフのエッジのサブセットです。図 6 は、最小全域木を取得するプロセスのアニメーションです。 アルゴリズム：
応用：
6. 強く連結されたコンポーネント 図7: 強く連結されたコンポーネント グラフ内のすべての頂点が他のすべての頂点を経由して到達できる場合、そのグラフは強く連結されています。図 7 には 3 つの強く接続されたコンポーネントが含まれており、頂点はそれぞれ赤、緑、黄色で表されます。 アルゴリズム：
応用：
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 の公開アカウントにご連絡ください。 |
<<: ドローン配送の価値は強調されていますが、完全に普及するには何が欠けているのでしょうか?
推薦する
このCVデータセットジェネレーターは人気があり、DeepMindなどが作成した13種類のCVタスクをサポートしています。
この記事はAI新メディアQuantum Bit（公開アカウントID：QbitAI）より許可を得て転載...
注目を浴びるAIとゲームは、どんな火花を散らすことができるのでしょうか？
[[202722]] 2005年、JJ Linは「Number 89757」で「人間を模倣した機械...
人工知能が VPS と共有ホスティング オプションの議論を再構築
人工知能は数え切れないほど多くの業界を前例のない形で変えています。ウェブホスティングは人工知能が関与...
誰もが今から準備すべき、2020 年のキャリアを変える 6 つのテクノロジー トレンド
[51CTO.com クイック翻訳] 新しいテクノロジーの導入により、私たちの職場は変化しています。...
人工知能、垂直農法、ブロックチェーン、ロボットは、未来の農業の急速な発展を推進する4つの主要技術である。
これは日本の東京国際展示場にあるデンソーの双腕協働ロボットの写真です。写真提供：新華社記者 華毅国連...
Google は、ユーザーにパーソナライズされたヘルプを提供するために、Bard を搭載したアシスタントをリリースしました。
海外メディアの報道によると、グーグルは10月7日、先日開催された「Made by Google 20...
LLaMA モデルは過去 3 か月間でどのように進化しましたか?指導の微調整の中心的な問題は何ですか?
Yao Fu (yao.fu@ed.ac.uk) は、エディンバラ大学の博士課程の学生です。彼は北...
AIが生成した写真は奇妙すぎますか?メリーランド大学とニューヨーク大学が共同でニューラルネットワークを解析、CLIPモデルのニューロンは頭蓋骨に似ている
AIのブラックボックスをどう解決するか？ニューラル ネットワーク モデルのトレーニング中、一部の R...
2019 年のインターネット キャンパス採用の給与が発表されました。いくらもらえるか見てみましょう!
2019年秋学期のキャンパスリクルートメントは終了に近づいています。近年、特にインターネット業界で...