BFS アルゴリズムを使用してグラフを探索し、最短パスを出力します
<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>
