BFS 알고리즘을 사용하여 그래프를 탐색하고 최단 경로를 출력합니다.
<p>이 프로그램의 목표는 다양한 공항을 통과하고 너비 우선 검색 알고리즘을 사용하여 PHX와 BKK 사이의 최단 경로를 출력하는 것입니다. <strong>하지만 결과를 인쇄하는 데 문제가 있습니다. </strong></p>
<p>예상되는 출력(최단 경로)은 다음과 같습니다. PHX -> LAX -> BKK</p>
<pre class="brush:php;toolbar:false;">const Airports = 'PHX BKK OKC JFK LAX MEX EZE HEL LOS LAP LIM'.split(' ');
const 경로 = [
['PHX', 'LAX'],
['PHX', 'JFK'],
['JFK', 'OKC'],
['JFK', '헬'],
['JFK', 'LOS'],
['MEX', 'LAX'],
['MEX', 'BKK'],
['멕스', '임'],
['MEX', 'EZE'],
['임', 'BKK'],
];
//그래프
const adjacencyList = new Map();
//노드 추가
함수 addNode(공항) {
adjacencyList.set(공항, []);
}
// 방향이 지정되지 않은 가장자리 추가
function addEdge(출발지, 목적지) {
adjacencyList.get(origin).push(destination);
adjacencyList.get(destination).push(origin);
}
// 그래프 생성
Airports.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 (queue.length > 0) {
const Airport = queue.shift(); // 대기열 변경
const 목적지 = adjacencyList.get(airport);
for (목적지의 상수 목적지) {
if (대상 === 'BKK') {
console.log(`BFS가 방콕을 찾았습니다!`)
//console.log(경로);
}
if (!visited.has(목적지)) {
방문.추가(목적지);
queue.push(대상);
}
}
}
}
bfs('PHX')
