Today I Learned

今日はグラフを整理し,グラフを探索するアルゴリズムを整理した.

グラフ＃グラフ＃

グラフは、ノードとノード、ノードとノードを接続する幹線からなる非線形データ構造です.

グラフィックのフィーチャーとツリーの比較

頂点は、複数のサブを有することができる.

図の幹線は、方向性(持たなくてもよい)、重み付けを有してもよい.

ツリーとは異なり、周期的に使用できます.

グラフィックの表示

グラフには大きく2つの表現があります.(もちろん、もっとあるかもしれませんが)

隣接リスト(隣接リスト)

隣接行列(隣接行列)

隣接リストと隣接マトリクス

隣接表は次のとおりです.

// adj[from][to] 형식의 인덱스로 나타낼 수 있다.
const adjacentList: Array<Array<number>> = [
  [],
  [2, 4],
  [1, 3],
  [1, 2],
  [3],
  [],
];

この表現は、幹線(u,v)を検出するのにO(n)の時間がかかるが、すべてのノードに対して、この表現はより有利である可能性がある.また、メモリの使用はほとんどありません.
隣接行列は以下のように表される.

/* adj[from][to] 형식의 인덱스로 나타낼 수 있다.
 * 연결된 간선은 1로, 그렇지 않으면 0으로 표현한다.
 */
const adjMatrix: Array<Array<number>> = [
  [0, 1, 0, 0, 0],
  [1, 0, 1, 1, 0],
  [0, 1, 0, 0, 0],
  [0, 1, 0, 0, 1],
  [0, 0, 0, 1, 0],
];

この表現の利点は,幹線(u,v)をO(1)にナビゲートできる時間であるが,ノードの数が多いほどメモリの消費量が多くなることである.そのため、場合によっては適当に使ったほうがいいです.

グラフィックナビゲーションアルゴリズム

方向性なし:

Union-find

幹線に重みがある場合:

フロイド・ウォーシェル

オセアニア

クラスタ(最小生成ツリー)

...

その他汎用機種

dfs(深さ優先ナビゲーション)

bfs(幅優先ナビゲーション)

すべてのグラフィックブラウズアルゴリズムの基礎は同じであるため,原理のみを整理し,残りは後で整理する.

次は幅優先探索の原理です.
1.最初のノードにアクセスします.
2.現在位置の幹線に接続されているすべての隣接ノードに移動します.
3.まだアクセスされていない隣接ノードが存在する場合、アクセス処理後、次のノードにアクセスします.
図から分かる重要な点は、図中の線がどんなに大きくても、図探索アルゴリズムによってアクセスする線を接続すれば、生成生成生成ツリーを生成できることである.

BFS、DFSの時間的複雑さ

通常最も多く用いられるBFS,DFSの時間的複雑度は隣接リストで表され,O(ノード数)+E(幹線数)の時間的複雑度を持つ.隣接行列で表すとO(N^2)の時間的複雑さがある.
実装の複雑さは、システムスタックを使用するdfsとは異なり、bfsは再帰的ではなくキューデータ構造を使用するため、少し複雑になる可能性がありますが、どのノードを参照してもスタックオーバーフローは発生しませんので、メモリの面で役立ちます.