너비 우선 검색 알고리즘이 잘못되었습니다.

php 에디터의 딸기 너비 우선 검색 알고리즘은 일반적으로 사용되는 그래프 순회 알고리즘이지만 경우에 따라 잘못된 결과가 나올 수 있습니다. 너비 우선 탐색 알고리즘은 일반적으로 그래프의 최단 경로 문제를 해결하는 데 사용됩니다. 핵심 아이디어는 시작 노드에서 시작하여 대상 노드를 찾거나 모든 노드를 탐색할 때까지 그래프의 노드를 레이어별로 탐색하는 것입니다. 그러나 너비 우선 탐색 알고리즘은 그래프에 순환이 있거나 대상 노드가 여러 개인 경우 올바른 결과를 얻지 못할 수 있습니다. 따라서 너비우선탐색 알고리즘을 사용할 때는 한계에 주의하고 특정 문제 시나리오에 따라 적절한 알고리즘을 선택해야 합니다.

질문 내용

어제 dfs에 관해 질문을 드렸습니다. 오늘은 bfs를 구현해보려고 합니다.

이 스레드에 제공되지 않은 .java 클래스는 이전 질문에서 가져온 것입니다.

내가 이 수업을 썼습니다:

breadthfirstsearch.java

으아아아

main.java 클래스에 다음을 추가했습니다.

으아아아

breadthfirstsearch.java 생성자의 경우 다음 행렬을 얻습니다.

으아아아 으아아아

처음에는 이러한 조건 중 어느 것도 참이 아니므로 건너뛸 수 있습니다.

으아아아

노드를 position=visited로 설정했기 때문에 다시 확인할 필요가 없습니다.

이러한 조건 중 (1)과 (3)만 true이므로 deque에 2개의 int[] 배열을 추가합니다.

으아아아

마지막으로 방문한 노드를 삭제합니다.

으아아아

출력 결과는 다음과 같습니다.

으아아아

그럼 코드는 어디에 있나요?

Solution

위치를 올바르게 처리하지 않습니다. 이 코드는 i:

을 변경합니다. 으아아아

c가 배열의 사본이라고 생각하는 것 같지만 사실은 아닙니다. c 是数组的副本，但事实并非如此。它仅引用 i 引用的数组，因此当您执行 c[0]++ 时，该单个数组现在具有该递增值。下次您应用此类代码时（在接下来的 if 块之一中），您将不会从原始位置开始，而是从已经变异的 i에서 참조하는 배열만 참조하므로 c[0]++를 수행하면 이제 해당 단일 배열에 증가된 값이 있습니다. 다음에 해당 코드를 적용하면(다음 if 블록 중 하나) 원래 위치에서 시작하지 않고 이미 변경된

에서 시작하므로 "step ”이 잘못된 위치로 이동하게 됩니다.

솔직히, 저는 이미 이전 질문에 대한 답변

에서 배열 유형 위치를 사용하는 아이디어가 덜 우아한 코드를 초래한다는 점을 지적했으며 이제 이를 통해 버그를 도입하는 것이 얼마나 쉬운지 알 수 있습니다.

이러한 배열을 사용하는 경우 실제로 새 배열을 구성하고 원본 배열의 내용을 복사해야 합니다.

다음은 코드의 이 부분을 수정한 것입니다. 🎜 으아아아

위 내용은 너비 우선 검색 알고리즘이 잘못되었습니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!