최단 경로 - BFS

a에서 저는 트리 데이터 구조의 두 가지 검색 알고리즘, 즉 깊이 우선 검색-DFS와 호흡 우선 검색-DFS를 논의했습니다. 가장 짧은 경로를 찾는 가장 효과적인 알고리즘은 BFS라고 말했습니다. 이 알고리즘은 뿌리부터 각 노드를 단계별로 훑어보고 DFS처럼 지점을 통해 대기열 임시 저장 노드를 사용하지 않습니다.다른 한편, DFS 알고리즘을 사용할 때는 반드시 완전히 하나씩 나누어야 하기 때문에 찾은 모든 해결 방안을 저장하고 최종적으로 가장 짧은 경로를 가진 해결 방안을 얻을 필요가 있다.

문제.
시작 단어와 끝 단어를 지정하려면 가장 짧은 경로를 찾아야 한다. 시작부터 끝까지 두 가지 규칙만 있고 가장 짧은 경로를 찾을 때 한 자모만 동시에 변경할 수 있으며 생성된 중간 단어는 단어 목록에 존재해야 한다.
참고: 이 블로그는 JavaByPatel blog의 JavaScript 버전입니다.
다음은 간단한 예입니다.
고양이
결국 입천장 이 터지다
리스트 = 고양이, 박쥐, 아기 침대, 톱니바퀴, 소, 쥐, 하지만, 컷, 개, 그물
경로는 다음과 같다. 고양이-쥐-박쥐-그런데 -COT-COG-DOG, 그러나 가장 짧은 경로는 고양이-COT-COG-DOG, BFS 알고리즘은 가장 짧은 경로를 통과할 수 있다. 다음은 이 알고리즘의 실현과 각자의 해석이다.
우선 한 단어에서 한 번에 한 자모만 바뀌었는지 확인하려면 다음과 같은 기능이 필요하다.

function differByOne(word, target) {
    if (word.length !== target.length) return false
    let diffCount = 0

    for (let i = 0; i < word.length; i++) {
        if (target.charAt(i) !== word.charAt(i))
            diffCount++
    }

    return diffCount === 1
}

그런 다음 BFS를 사용하여 가장 짧은 경로를 찾습니다.

function checkWords(words, start, target) {
    if (!words.has(start) || !words.has(target)) return null

    const queue = []
    const path = []

    path.push(start)
    queue.push(path)
    words.delete(start)

    while (queue.length) {
        const lastPath = queue.shift()
        const lastWord = lastPath[lastPath.length - 1]

        if (target == lastWord) return lastPath

        for (let item of words) {
            if (differByOne(item, lastWord)) {
                const newPath = [...lastPath]
                newPath.push(item)
                queue.push(newtPath)
                words.delete(item)
            }
         }
    }

    return null
}

checkWords 함수는 3개의 매개 변수를 수신하는데 첫 번째는 단어 목록이다. 이것은 데이터 형식 집합, 시작과 목표 단어이다.

단어 목록에 알파벳이나 목표 단어가 포함되지 않는지 확인하고null로 바로 돌아가기(!Words.has(start)||||!말.있다

가장 짧은 경로를 저장하는 대기열로 사용할 수 있는 그룹을 설명합니다.

선택한 단어를 저장하기 위해 path라는 그룹을 표시합니다.

경로, 시작 단어, 경로에 추가합니다.밀어냄(시작).

대기열에 새 경로를 추가합니다.

첫 번째로 선택한 단어를 삭제합니다.단어 목록에서 삭제(시작)합니다.

대기열에 데이터가 있으면 (queue.length) 다음과 같은 동작을 수행합니다.

대기열에서 첫 번째 경로 (단어 목록) 를 삭제하고lastPath 상수로 되돌려줍니다.

마지막으로 선택한 단어는 이전 단계에서 얻은 단어 목록에서 얻습니다. const lastWord=lastPath[lastPath.length-1].

마지막으로 선택한 단어가 검색 중인 마지막 단어라면 얻은 단어 목록 (최단 경로) 을 되돌려줍니다. (target==lastWord) lastPath를 되돌려줍니다. 만족하지 않으면 다음 설명을 계속 실행합니다.

단어표의 모든 단어에 대해 다음과 같은 조작을 했다.

단어 목록에 있는 현재 단어(항목)가 마지막 선택한 단어(lastWord)와 알파벳이 다른지, 단어(항목,lastWord)가 다른지 확인합니다.

이전 조건이 충족되면 마지막으로 찾은 경로를 포함하는 단어(단어 목록 -lastPath) const newPath=[...lastPath]를 포함하는 새 목록(새 경로)을 만듭니다.

이전 newPath에서 설명한 조건을 충족하는 새 경로를 가리킵니다.밀어넣기(항목)를 추가합니다.

새 경로가 대기열에 추가되었습니다.밀어냄(새 경로).

단어 목록에서 선택한 단어를 삭제합니다.삭제(항목).

중복 주기 중 최종 단어를 찾지 못하면null로 돌아갑니다.

완성!,상술한 알고리즘의 기능을 테스트할 때가 되었다. 아래와 같다.

const words = new Set(['BUT', 'CUT', 'RAT', 'BAT', 'WEB', 'CAT', 'COT', 'COG', 'COW', 'DOG'])
const start = 'CAT'
const target = 'DOG'

console.log(checkWords(words, start, target))

// output
// ["CAT", "COT", "COG", "DOG"]

앞의 코드는 checkWords 함수를 호출하여 Set 형식의 데이터 구조로 단어 목록을 보내고 초기 단어와 목표 단어를 검색한 결과를 컨트롤러에 출력합니다.결과는 시작 단어에서 끝까지의 가장 짧은 경로가 될 것이다.
소스 코드는 GitHub에 있습니다.
쓸모가 있습니까?당신의 지지를 표현하고 공유하세요.
안전에 주의하세요. 읽어 주셔서 감사합니다.