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

hizengzeng 发布于2019-08-21 11:54 / 2178人阅读

摘要：前端在开发过程中接触到的算法最多的莫过于排序和深度优先遍历。关于算法的遍历过程，我简略的画了一个示例图实例最近在实际业务场景中，跟后端约定页面中所有组件的消息根据页面上的组件聚合到一个对象中，后端返回的是类似如下的一个树形数据结构。

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);

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

云服务器 GPU云服务器矩阵dfs算法描述的数据结构与算法 dfs生存分析需要的数据 php与前端的交互

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/87261.html

算法（第4版） Chapter 4.2 有向图

摘要：只好特地拎出来记录证明一下算法步骤第一步在逆图上运行，将顶点按照逆后序方式压入栈中显然，这个过程作用在有向无环图上得到的就是一个拓扑排序作用在非上得到的是一个伪拓扑排序第二步在原图上按第一步的编号顺序进行。等价于已知在逆图中存在有向路径。 Algorithms Fourth EditionWritten By Robert Sedgewick & Kevin WayneTranslat...

曹金海 2019-08-14 17:13 评论0 收藏0
PHP面试：常见查找算法一篇说透

摘要：我们现在来看二分搜索算法的两种变形插值搜索和指数搜索。插值搜索是对二分搜索算法的改进，插值搜索可以基于搜索的值选择到达不同的位置。预警在本篇文章中，将为各位老铁介绍不同的搜索算法以及它们的复杂度。因为力求通俗易懂，所以篇幅可能较长，大伙可以先Mark下来，每天抽时间看一点理解一点。本文配套的Github Repo，欢迎各位老铁star，会一直更新的。开篇和排序类似，搜索或者叫做...

付永刚 2019-07-01 10:47 评论0 收藏0
随机生成指定面积单连通区域

摘要：原文链接最近在知乎上看到一个问题，随机生成指定面积单连通区域，感觉还挺有意思的，于是整理一下写一篇新文章。问题阐述如下图所示，在的区域中，随机生成面积为的单连通区域，该随机包括位置随机以及形状随机。原文链接：https://xcoder.in/2018/04/01/random-connected-area/ 最近在知乎上看到一个问题，「随机生成指定面积单连通区域？」，感觉还挺有意...

zhoutk 2019-08-22 16:00 评论0 收藏0
算法（第4版） Chapter 4.1 无向图

摘要：边仅由两个顶点连接，并且没有方向的图称为无向图。用分隔符当前为空格，也可以是分号等分隔。深度优先算法最简搜索起点构造函数找到与起点连通的其他顶点。路径构造函数接收一个顶点，计算到与连通的每个顶点之间的路径。 Algorithms Fourth EditionWritten By Robert Sedgewick & Kevin WayneTranslated By 谢路云Chapter...

kamushin233 2019-08-14 17:14 评论0 收藏0