BFS アルゴリズムを使用してグラフを探索し、最短パスを出力します
P粉633075725
2023-09-03 11:42:48
<p>プログラムの目標は、さまざまな空港を通過し、幅優先検索アルゴリズムを使用して PHX と BKK 間の最短経路を出力することです。 <strong>しかし、結果を印刷するのに問題があります。 </strong></p>
<p>予想される出力 (最短パス) は次のとおりです: PHX -> LAX -> MEX -> BKK
<pre class="brush:php;toolbar:false;">const Airport = 'PHX BKK OKC JFK LAX MEX EZE HEL LOS LAP LIM'.split(' ');
const ルート = [
['PHX'、'LAX']、
['PHX'、'JFK']、
['JFK'、'OKC']、
['JFK'、'ヘル']、
['JFK'、'LOS']、
['メキシコ'、'ロサンゼルス']、
['メキシコ'、'BKK']、
['MEX', 'LIM'],
['MEX'、'EZE']、
['リム'、'BKK']、
];
//グラフ
const adjacencyList = new Map();
//ノードを追加
関数 addNode(空港) {
adjacencyList.set(空港, []);
}
// エッジを無向に追加します
関数 addEdge(起点, 終点) {
adjacencyList.get(origin).push(destination);
adjacencyList.get(目的地).push(出発地);
}
// グラフを作成する
Airport.forEach(addNode);
// 各ルートをループし、値を addEdge 関数に展開します
Routes.forEach(route => addEdge(...route));</pre>
<p>ノードを開始点 (サイト)、エッジを目的地として、グラフは無向です。</p>
<pre class="brush:php;toolbar:false;">function bfs(start) {
const 訪問 = new Set();
Visited.add(start); // 開始ノードを訪問済みリストに追加します
const キュー = [開始];
while (キューの長さ > 0) {
const Airport = queue.shift(); // キューを変更します
const destinations = adjacencyList.get(空港);
for (宛先のconst宛先) {
if (宛先 === 'BKK') {
console.log(`BFS がバンコクを発見しました!`)
//コンソール.ログ(パス);
}
if (!visited.has(目的地)) {
訪問済み.追加(目的地);
キュー.プッシュ(宛先);
}
}
}
}
bfs('PHX')</pre></p>
![[Web フロントエンド] Node.js クイック スタート](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
コメント内の InSync の提案に従って問題を解決できました。
bfs() 関数では、各ノード (親ノード) がたどるパスを保存するために oldpath が使用され、結果を保存するために最短パスが使用されます。 リーリー リーリー新しい関数の機能は非常に単純です。親ノードを ShortestPath に追加し、親ノードの親ノード (存在する場合) を検索します。現在の親ノードがルート ノードである場合、ループは終了します
リーリーノードを訪問済みとしてマークする代わりに、この機会を利用してノードをその親でマークします。マップを使用して次のことができます:
また、関数内でグローバル変数を参照することを避け、代わりに必要なものすべてを引数として渡すことをお勧めします。