BFS 알고리즘을 사용하여 그래프를 탐색하고 최단 경로를 출력합니다.
P粉633075725
2023-09-03 11:42:48
<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')
![[웹 프런트엔드] Node.js 빠른 시작](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
InSync의 댓글 제안을 따라 문제를 해결할 수 있었습니다
bfs() 함수에서 oldpath는 각 노드(부모 노드)가 이동한 경로를 저장하는 데 사용되고 최단 경로는 결과를 저장하는 데 사용됩니다
으아악 으아악새 함수의 기능은 매우 간단합니다. shortestPath에 상위 노드를 추가한 다음 상위 노드의 상위 노드를 찾고(존재하는 경우) 현재 상위 노드가 루트 노드일 때 루프가 종료됩니다. 으아악
노드를 방문한 것으로 표시하는 대신 이 기회를 이용하여 노드를 상위 노드로 표시하세요. 지도를 사용하여 다음을 수행할 수 있습니다.
또한 함수에서 전역 변수를 참조하는 것을 피하고 대신 필요한 모든 것을 매개변수로 전달하는 것이 좋습니다.