广度优先遍历（BFS）和深度优先遍历（DFS）

[kekobin]

以如下html片段为例，分别说明BFS和DFS的区别。

<div id="app">
	<ul id="ulTest">
		<li class="li-class">
			<p class="li-item-p">this is li item p</p>
		</li>
		<li class="li-class">li item 1</li>
		<li class="li-class">li item 2</li>
		<li class="li-class">li item 3</li>
	</ul>
</div>

DFS

指的是先将当前节点的孩纸节点遍历完，然后再去遍历同级节点，常见的有两种实现方式：

• （1）递归算法

function deepTraversal(node, nodelist) {
	if(node) {
		nodelist.push(node);

		const { children } = node;

		for(let i=0;i<children.length; i++) {
			// 相当于从最左侧分支遍历，然后中间，最后右边
			deepTraversal(children[i], nodelist)
		}
	}

	return nodelist;
}

• (2) 非递归算法

function deepTraversal(node) {  
    const nodeList = [];  
    if (node) {  
        const stack = [];  
        stack.push(node);  
        while (stack.length != 0) {  
            const item = stack.pop();  
            nodeList.push(item);  
            const { children } = item;
              
            for (let i = children.length - 1; i >= 0; i--) {
                stack.push(children[i]);
            }  
        }  
    }    
    return nodeList;  
} 

应用于上面的示例如下图所示：

结果如下：

BFS

指的是先依次遍历兄弟节点，然后遍历兄弟节点下的子节点。

主要使用到了二叉树算法来进行遍历：即先左孩纸，然后右孩纸。

function wideTraversal(node) {
	const nodes = [];

	if(node) {
		const quene = [];
		quene.push(node);

		while(quene.length !== 0) {
			const n = quene.shift()

			nodes.push(n)
			const children = n.children

			for(let i=0;i<children.length;i++) {
				quene.push(children[i])
			}
		}
	}	

	return nodes;
}

上例示例如下：

结果如下：