이 글은 JavaScript 깊이 우선 순회(DFS) 및 너비 우선 순회(BFS) 알고리즘에 대해 소개합니다. 도움이 필요한 친구들이 참고할 수 있기를 바랍니다. .
배경: 페이지를 개발할 때 때때로 다음과 같은 요구 사항에 직면합니다. 페이지의 특정 DOM 노드를 탐색하여 대상 DOM 노드를 찾습니다. 일반적인 접근 방식은 document.getElementById(), document.getElementsByName() 또는 document 선택기를 사용하는 것입니다. .getElementsByTagName()이지만 이 기사에서는 알고리즘 관점에서 dom 노드를 찾고 동시에 깊이 우선 탐색(DFS) 및 너비 우선 탐색(BFS)의 원리를 이해합니다.
준비
페이지의 DOM 구조가 다음과 같다고 가정해 보겠습니다.
<div> <ul> <li> <a> <img 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="https://img.php.cn/upload/image/727/585/757/1553909199320348.png" 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="//m.sbmmt.com/course/list/17.html" target="_blank">JavaScript Video Tutorial</a> 칼럼을 주목하세요! </p><p></p>위 내용은 JavaScript 깊이 우선 순회(DFS) 및 너비 우선 순회(BFS) 알고리즘 소개의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!
![[웹 프런트엔드] Node.js 빠른 시작](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
