JavaScript 깊이 우선 순회(DFS) 및 너비 우선 순회(BFS) 알고리즘 소개

이 글은 JavaScript 깊이 우선 순회(DFS) 및 너비 우선 순회(BFS) 알고리즘에 대해 소개합니다. 도움이 필요한 친구들이 참고할 수 있기를 바랍니다. .

배경: 페이지를 개발할 때 때때로 다음과 같은 요구 사항에 직면합니다. 페이지의 특정 DOM 노드를 탐색하여 대상 DOM 노드를 찾습니다. 일반적인 접근 방식은 document.getElementById(), document.getElementsByName() 또는 document 선택기를 사용하는 것입니다. .getElementsByTagName()이지만 이 기사에서는 알고리즘 관점에서 dom 노드를 찾고 동시에 깊이 우선 탐색(DFS) 및 너비 우선 탐색(BFS)의 원리를 이해합니다.

준비

페이지의 DOM 구조가 다음과 같다고 가정해 보겠습니다.

<div>
    <ul>
        <li>
            <a>
                <img  src="/static/imghwm/default1.png" data-src="" class="lazy" alt="JavaScript 깊이 우선 순회(DFS) 및 너비 우선 순회(BFS) 알고리즘 소개" >
            </a>
        </li>
        <li>
            <span></span>
        </li>
        <li>
        </li>
    </ul>
    <p></p>
    <button></button>
</div>

이 DOM 구조를 트리로 변환해 보겠습니다

이후에는 DOM 구조가 훨씬 더 명확해진 것 같습니다.

깊이 우선 검색

이 방법은 DOM 노드에서 시작하여 모든 하위 노드가 형제 노드를 탐색할 때까지 하위 노드를 탐색하면서 수직 차원에서 DOM 트리를 탐색합니다. 그림에 표시된 대로(순회 순서는 빨간색 자물쇠 표시입니다):

js 알고리즘 코드 구현(재귀 버전):

function deepFirstSearch(node,nodeList) {  
    if (node) {    
        nodeList.push(node);    
        var children = node.children;    
        for (var i = 0; i <p>비재귀 버전: </p><pre class="brush:php;toolbar:false">function deepFirstSearch(node) {
    var nodes = [];
    if (node != null) {
        var stack = [];
        stack.push(node);
        while (stack.length != 0) {
        var item = stack.pop();
        nodes.push(item);
        var children = item.children;
        for (var i = children.length - 1; i >= 0; i--)
            stack.push(children[i]);
        }
    }
    return nodes;
}

deepFirstSearch는 두 개의 매개변수를 허용합니다. 매개변수는 순회해야 하는 노드이고, 두 번째는 노드에 저장된 배열이며, 순회 후 배열이 반환됩니다. 순회 순서는 다음과 같습니다.

let root = document.getElementById('root')
deepTraversal(root,nodeList=[])

Console 메소드를 호출합니다. 출력 결과

너비 우선 순회(breadth-first traverse)

이 방법은 노드의 첫 번째 하위 노드부터 시작하여 모든 형제 노드를 순회한 다음 DOM 트리를 수평 차원으로 순회합니다. 이 순회 후에는 당분간 깊이 들어가지 않고 형제 노드의 하위 노드 순회를 시작합니다. 그림과 같이(순회 순서는 빨간색 자물쇠 표시로 표시됨):

js 구현 알고리즘 코드(재귀 버전):

function breadthFirstSearch(node) {
    var nodes = [];
    var i = 0;
    if (!(node == null)) {
        nodes.push(node);
        breadthFirstSearch(node.nextElementSibling);
        node = nodes[i++];
        breadthFirstSearch(node.firstElementChild);
    }
    return nodes;
}

BFS의 재귀 버전은 레벨이 너무 깊어서 스택 오버플로가 발생합니다. : 최대 호출 스택 크기를 초과했지만 순회 순서에는 여전히 문제가 없습니다. 순회 과정 중에 순회된 배열을 반환하지 않고도 작업을 수행할 수 있습니다.

비재귀 버전:

function breadthFirstSearch(node) {  
    var nodes = [];  
    if (node != null) {  
        var queue = [];  
        queue.unshift(node);  
        while (queue.length != 0) {  
            var item = queue.shift();  
            nodes.push(item);  
            var children = item.children;  
            for (var i = 0; i <p>콘솔 출력 결과: </p><p><img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/image/727/585/757/1553909199320348.png?x-oss-process=image/resize,p_40" class="lazy" title="1553909199320348.png" alt="JavaScript 깊이 우선 순회(DFS) 및 너비 우선 순회(BFS) 알고리즘 소개"></p><p   style="max-width:90%">요약: BFS와 DFS는 모두 비교적 간단하며 방향이 없고 연결되지 않은 그래프입니다. 향후 더 많은 JavaScript 기반 알고리즘이 업데이트될 예정입니다. </p><p style="white-space: normal;">이 기사는 여기까지입니다. 더 많은 흥미로운 콘텐츠를 보려면 PHP 중국어 웹사이트의 <a href="http://www.php.cn/course/list/17.html" target="_blank">JavaScript Video Tutorial</a> 칼럼을 주목하세요! </p><p></p>

위 내용은 JavaScript 깊이 우선 순회(DFS) 및 너비 우선 순회(BFS) 알고리즘 소개의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!