幅優先ナビゲーション

2454 ワード

幅優先ナビゲーションアルゴリズム#アルゴリズム# テキストリンク

グラフ＃グラフ＃

グラフは、接続の集合をモデル化します.
グラフィックは頂点(node)と幹線(edge)からなり、頂点は複数の異なる頂点に直接接続できます.このように続く頂点を隣人と呼ぶ.したがって、2は1の隣人である.

最短経路問題を解くアルゴリズムです.

最短パスを整理すると2つの質問に答えることができます.
1.頂点aから頂点bへのパスは存在しますか?
2.頂点aから頂点bへの最短パスは何ですか.

キュー(キュー)は、挿入や削除などの演算を使用するキュー内の要素に任意にアクセスできません.

グラフ表現はハッシュ表が使えます!
ハッシュ・テーブルを使用すると、キーに値を指定できます.この場合、ある頂点に隣接する頂点を指定するだけでいいです.
たとえば、次のコードです.

let graph = {};
graph["I"] = ["alice", "bob", "claire"];

アルゴリズムの実現方式は以下の通りである.

確認者リストの列に入れる準備をします.

キューから1人を取り出す

当該人が条件

に適合していることを確認する.

2YES?ジョブ完了|NO?は、隣接するすべてをキューに追加します.

2回繰り返します.

キューが空の場合、グラフには条件を満たす人はいません.

キューを更新するときにpushとpopを使用します!
JavaScriptのDequeをまとめました。

幅優先ナビゲーションは、aからbへのパスがあるかどうかを示します.

パスが存在する場合、最短パスも見つかります.

xへの最短経路が見つかったという問題があれば、この問題をグラフィカル化された幅優先スタンプで解く.

方向図は矢印を有し、矢印方向に関係する.

の無方向グラデーション矢印はなく、両者の相互関係を表す.

キューは先入先出です.

スタックは後入先出です.

探索車に増加した順に人を確認する.したがって、ナビゲーションリストはキューである必要があります.最短パスが見つかりません.

人の人を確認した後、二度と確認しないでください.無限の繰り返しになるからだ.

リファレンス
『Hello Codingアルゴリズム』を勉強してまとめた内容です.

この問題について(幅優先ナビゲーション), 我々は、より多くの情報をここで見つけました https://velog.io/@gay0ung/너비-우선-탐색

テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。

Collection and Share based on the CC Protocol