グラフのデータ構造 のコレクションです ノード によって接続されています エッジ 。異なるエンティティ間の関係を表すために使用されます。 グラフアルゴリズム グラフの操作と分析に使用されるメソッドで、次のようなさまざまな問題を解決します。 最短経路を見つける または サイクルを検出しています。
ローカル日時Java
目次
- グラフの構成要素
- グラフの基本操作
- グラフの応用
- グラフの基礎
- グラフ内の BFS と DFS
- グラフ内のサイクル
- グラフ内の最短パス
- 最小スパニングツリー
- トポロジカルソート
- グラフの接続性
- グラフの最大流量
- グラフ上の問題を実行する必要がある人もいます
- いくつかのクイズ
グラフの構成要素:
- 頂点: 頂点はグラフの基本単位です。頂点は、頂点またはノードとしても知られる場合があります。すべてのノード/頂点にはラベルを付けることも、ラベルを付けないこともできます。
- エッジ: エッジは、グラフの 2 つのノードを接続するために描画または使用されます。有向グラフ内のノードのペアを順序付けすることができます。エッジは、任意の方法で任意の 2 つのノードを接続できます。ルールはありません。エッジは円弧とも呼ばれる場合があります。すべてのエッジにラベルを付ける/ラベルを付けないことができます。
グラフの基本操作:
グラフに対する基本的な操作は次のとおりです。
- グラフへのノード/エッジの挿入 – グラフにノードを挿入します。
- グラフ内のノード/エッジの削除 – グラフからノードを削除します。
- グラフの検索 – グラフ内のエンティティを検索します。
- グラフの走査 – グラフ内のすべてのノードを走査します。
グラフの応用:
実際のアプリケーションは次のとおりです。
- グラフ データ構造を使用して、パス、ショット、タックルなど、チーム内のプレーヤー間の相互作用を表すことができます。これらのやり取りを分析すると、チームのダイナミクスと改善の余地についての洞察が得られます。
- 一般に、ソーシャル メディア上の友人のネットワークなど、ソーシャル ネットワークを表すために使用されます。
- グラフを使用すると、ルーターとスイッチ間の接続など、コンピューター ネットワークのトポロジを表すことができます。
- グラフは、道路や空港など、交通ネットワーク内のさまざまな場所間の接続を表すために使用されます。
- グラフはニューラル ネットワークで使用され、頂点がニューロンを表し、エッジがニューロン間のシナプスを表します。ニューラル ネットワークは、私たちの脳がどのように機能し、学習時に接続がどのように変化するかを理解するために使用されます。人間の脳には、約 10^11 個のニューロンと 10^15 個近くのシナプスがあります。
グラフの基本:
グラフ内の BFS と DFS:
- グラフの幅優先トラバーサル
- グラフの深さ優先探索
- 深さ優先検索の応用
- 幅優先トラバーサルの応用
- 反復深さ優先検索
- 切断されたグラフの BFS
- DFS を使用したグラフの推移的閉包
- BFSとDFSの違い
グラフ内のサイクル:
- 有向グラフでのサイクルの検出
- 無向グラフのサイクルを検出する
- 色を使用した直接グラフのサイクルを検出
- グラフ内の負のサイクルを検出 | （ベルマン・フォード）
- 無向接続グラフにおける長さ n のサイクル
- フロイド・ウォーシャルを使用した負のサイクルの検出
- 有向非巡回グラフのクローンを作成する
- Union-Find アルゴリズムにおけるランク別ユニオンおよびパス圧縮
- グラフ内の最短パス:
- ダイクストラの最短経路アルゴリズム
- ベルマン・フォードアルゴリズム
- フロイド・ウォーシャルのアルゴリズム
- ジョンソンの全ペア最短経路アルゴリズム
- 有向非巡回グラフの最短パス
- ダイヤルのアルゴリズム
- 多段グラフ（最短経路）
- 重み付けされていないグラフの最短パス
- Karp の最小平均 (または平均) 体重サイクル アルゴリズム
- 0-1 BFS (バイナリ重みグラフの最短パス)
- 無向グラフで最小加重サイクルを見つける
最小スパニング ツリー:
- Prim の最小スパニング ツリー (MST)
- Kruskal の最小スパニング ツリー アルゴリズム
- MST における Prim のアルゴリズムと Kruskal のアルゴリズムの違い
- 最小スパニングツリー問題の応用
- すべての都市を接続するための最小コスト
- グラフ内のスパニング ツリーの総数
- 最小プロダクトスパニングツリー
- 最小スパニング ツリーの逆削除アルゴリズム
- Boruvka の最小スパニング ツリーのアルゴリズム
トポロジカルソート:
- トポロジカルソート
- 有向非巡回グラフのすべてのトポロジカルな種類
- トポロジカルソートのためのカーンのアルゴリズム
- DAG を維持するために DAG に追加できるエッジの最大数
- 有向非巡回グラフの最長パス
- 頂点の出発時刻を使用したグラフのトポロジカルソート
グラフの接続性:
- グラフ内のアーティキュレーション ポイント (またはカット頂点)
- 二重接続コンポーネント
- グラフ内の橋
- オイラー経路と回路
- オイラー経路または回路を印刷するための Fleury のアルゴリズム
- 強く接続されたコンポーネント
- 正確に k 個のエッジを持つソースから宛先までの可能なウォークをすべてカウントします。
- 有向グラフのオイラー回路
- ターゲット単語に到達するまでの最短のチェーンの長さ
- 文字列の配列を連鎖して円を形成できるかどうかを調べる
- 強く接続されたコンポーネントを見つけるための Tarjan のアルゴリズム
- 各エッジを使用して各ノードを移動するパス (ケーニヒスベルクの七つの橋)
- 動的な接続性 |セット 1 (増分)
グラフ内の最大流量:
- 最大流量問題の概要
- 最大流量問題のための Ford-Fulkerson アルゴリズム
- 2 つの頂点間の互いに素なエッジ パスの最大数を見つける
- 流れネットワーク内の最小 s-t カットを見つける
- 最大二部マッチング
- チャンネル割り当ての問題
- プッシュ再ラベルアルゴリズムの概要
- Karger のアルゴリズム - セット 1 - 導入と実装
- Dinic の最大流量アルゴリズム
グラフ上で問題を実行する必要がある人もいます。
- ブール行列の最大領域の長さを求める
- 森の中の木の数を数える
- ピーターソングラフの問題
- 無向グラフのクローンを作成する
- グラフの色付け (導入と応用)
- 巡回セールスマン問題 (TSP) の実装
- 頂点カバーの問題 |セット 1 (導入と近似アルゴリズム)
- K センター問題 |セット 1 (貪欲な近似アルゴリズム)
- Erdos Renyl モデル (ランダム グラフ生成用)
- 中国の郵便配達員またはルート検査 |セット 1 (導入)
- 有向グラフ用の Hierholzer のアルゴリズム
- 指定されたグラフが二部グラフであるかどうかを確認する
- 蛇とはしごの問題
- Boggle (文字ボード内で考えられるすべての単語を見つけます)
- 最大マッチングのための Hopcroft Karp アルゴリズム - はじめに
- すべてのオレンジが腐るまでの最短時間
- すべての頂点の指定された次数からグラフを構築します
- 有向グラフにユニバーサル シンクが存在するかどうかを判断する
- グラフ内のシンク ノードの数
- 2 クリーク問題 (グラフが 2 つのクリークに分割できるかどうかを確認する)
いくつかのクイズ:
- グラフトラバーサルに関するクイズ
- グラフ最短経路に関するクイズ
- グラフ最小スパニングツリーに関するクイズ
- グラフに関するクイズ
クイックリンク ：
- 深さ優先検索 (DFS) に関する面接での質問トップ 10
- いくつかの興味深い最短経路の質問
- グラフに関するビデオ
推奨：
- データ構造とアルゴリズムを学ぶ | DSA チュートリアル