前端的数据结构与算法（1）-- dfs

[zwhu]

dfs

前端在开发过程中接触到的算法最多的莫过于排序和 dfs(深度优先遍历) 。 dfs 算法广泛用于图（树是图的一种）的遍历，如：没有 querySelectorAll 的时候，根据 classname 或者 tag 查找 element。

关于 dfs 算法的遍历过程，我简略的画了一个示例图：

实例：

最近在实际业务场景中，跟后端约定页面中所有组件的消息根据页面上的组件 id 聚合到一个对象中，后端返回的是类似如下的一个树形数据结构。前端需要把所有的错误信息都拿出来，按照页面上所有组件的顺序聚合显示在一个全局信息面板组件上（至于按照组件顺序排序算法本文暂且略过）

let tree = {
    'id1': {
		message: 'hello'
	},
	'id2': {
		message: 'world',
		children: {
		  'id2-1': {
			  message: 'haha',
			  children: {
			  }
		  },
		  'id2-2': {
			  message: 'heihei'
		  }
		}
	}
}

由于某些大组件可能是由多个小组件层层嵌套组合而来，且每个小组件都有相应的 message 需要展示，所以就选择了上述的树形结构来表达组件的信息。这个时候就会有人问，为什么不让后端把所有 message 都聚合到数组里面？因为前端不仅需要把这些错误信息聚合到一起展示，也需要把错误定位到具体组件上

递归版本实现

function dfs(tree = {}, messages = []) {
	let i = 0;
	if(!messages) messages = [];
	if(tree.message) messages.push(tree.message);
	
	const keys = Object.keys(tree.children || {});
	while (i < keys.length) {
		dfs(tree.children[keys[i]], messages);
		i += 1;
	}
	return messages;
}

 tree = {
	message: null,
	children: tree
 };  
 
 dfs(tree);

非递归版本实现

  function dfs(tree = {}) {
	const array = [tree];
	let messages = [];
	while (array.length) {
	  const top = array.pop();
	  if (top.message) {
		messages.push(top.message);
	  }
	  const keys = Object.keys(top.children || {});
	  let i = keys.length;
	  while (i > 0) {
		i -= 1;
		array.push(top.children[keys[i]]);
	  }
	}
	return messages
  }
  
 tree = {
	message: null,
	children: tree
 };  
 
 dfs(tree);

在实际使用中，考虑到数据结构的层数没那么多，其实尾递归版本和非递归版本所消耗的时间在浏览器的优化下几乎可忽略了。