积累·1117

JavaScript 算法基础

成年人的成长在于一次次的积累

# 深度优先遍历和广度优先遍历

简单了解两种遍历方式的定义,实现以及不同点.

# 深度优先遍历

Depth-First-Search(DFS),深度优先遍历属于图算法的一种,其过程简单的说就是对每一个可能的分支路径深入到不能再深入为止,且每个节点只能访问一次. 基本思路: 从图的某一个顶点v开始访问:

  • 访问顶点v;
  • 依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问；
  • 此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。

大多数人往往觉得算法有些不好理解或不易掌握使用，原因一般都是没找对方式方法。先抛去算法的具体由来，我们会先从定出出发，找寻合适的数据结构，通过对该数据结构进行特殊的操作从而达到目的，这个操作过程就是代码实现的理论基础。就那深度优先遍历举例：

  • 我们需要先确定一个顶点作为起点，然后访问他的第一个子节点，然后将该子节点作为起点，再从访问他的第一个子节点，若无子节点，则将第二个子节点作为起点，重复上述过程，直至遍历所有节点。 发现上述过程有一个特点都是操作第一个子节点（都将操作节点当做起点），这不就是栈这种数据结构的特点吗？数据进出都在栈顶操作。那我们就尝试用栈来实现上次操作。
  • 将根节点压入栈中；
  • 将栈顶元素弹出，遍历该元素的所有下一级子元素，并所有子元素再压入栈中，并把该元素标记为其下一级元素的前驱。
  • 重复上两步，直至遍历所有顶点。
<body>
  <div class="parent">
    <div class="child-1">
      <div class="child-1-1">
        <div class="child1-1-1">
          a
        </div>
      </div>
      <div class="child-1-2">
        <div class="child-1-2-1">
          b
        </div>
      </div>
      <div class="child-1-3">
        c
      </div>
    </div>
    <div class="child-2">
      <div class="child-2-1">
        d
      </div>
      <div class="child-2-2">
        e
      </div>
    </div>
    <div class="child-3">
      <div class="child-3-1">
        f
      </div>
    </div>
  </div>
</body>

针对上面的HTML片段.使用深度优先遍历方式访问所有节点.

const deep2 = (node) => {
  let stack = []; //创建一个栈,进出都在栈顶完成.我们用数组模拟栈，数组尾部为栈顶
  let nodeList = [];
  if (node) {
    stack.push(node); // 将节点放置栈中.
    while (stack.length) { //当栈中有数据时
      let item = stack.pop(); // 将栈顶数据推出(第一次操作即取节点组的根节点出来)
      nodeList.push(item); // 将栈顶数据放置list中
      let children = item.children || item[0].children || []; // 取栈顶节点的子节点 
      for (let i = children.length - 1; i >= 0; i--) {
        stack.push(children[i])  // 将子节点倒序放置栈中，保证栈顶是第一个子节点
      }
    } 
  }
  return nodeList
}

递归写法
const deep1 = (node,nodeList = []) => {  // node是html片段,nodeList是所有节点的集合数组.
  if(node !== null) {
    nodeList.push(node);
    let children = node.children;
    for (let i = 0; i < children.length; i++){
      deep1(children[i],nodeList)
    }
  }
  return nodeList;
}

深度优先遍历换言之就是一条路走到黑直到该节点下没有子节点为止.

# 广度优先遍历

Breadth First Search(BFS)又称宽度优先遍历,和上面的深度优先遍历刚好是两个不同维度上的搜索算法.也是最基础的图算法之一,很多算法都是以BFS为原型的,如狄杰斯特拉算法求最短路径、Prim算法求最小生成树等.BFS算法是一种盲选法,是不考虑结果的一种算法.从某一顶点v起开始遍历,然后遍历与v相邻的顶点,依次访问相邻顶点,如果此时图中尚有顶点未被访问，则需要另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。

同样从定义--数据结构--代码实现来看一广度优先遍历： 首先确定一个起点v，访问该顶点的某一个临点，然后再访问起点的剩余临点，直至第一个起点没有未被访问的临点位置。（到现在v的所有临点已经全部遍历）然后选取一个未被访问的顶点再作为起点重复上述步骤，直至全部顶点被遍历。

这里的操作没有明显的指向哪一种数据结构，我们仔细分析一下，其实广度优先遍历就做了两件事，一是遍历某一顶点的所有临点，二是取为被遍历的点作为新起点（这里就就可以当做一个新的图或树来看）。简单的说就将图或树按某种方式分隔成为多个图或树来进行同一种操作。~由于是按相邻关系遍历，就具有线性表的前驱后继性~。有点类似于流水线操作，第一步我只遍历临点，不管是否有子节点，不管顶点处于什么位置，第二步将分隔一个新的图出来继续回到第一步，有点首尾循环的感觉。在头部1进行遍历节点，在尾部分隔出新图。既能在顶部也能在尾部进行操作的线性表不就是是队列吗？那我们尝试用队列（只能在头部删除，尾部添加）来实现：

  • 将根节点放置在队尾（此时只有一个元素，队尾==队首）
  • 取队首的一个元素，遍历该元素的所以子元素，并将子元素放置队尾，该元素标记为子元素的前驱。
  • 重复上述两步，直至遍历所有顶点。
const width = (node) => {
  let queue = []; // 创建一个队列，我们使用数组
  let nodeList = []; // 存放遍历结果
  if(node) {  // 当根节点存在
    queue.push(node); // 节点进入队列尾部
    nodeList.push(node);
    if(queue.length) {
      let item = queue.shift(); // 取队首元素
      nodeList.push(item);
      let children = item.children || item[0].children || []; // 取队首元素的子元素
      for(let i = 0; i <= children.length-1; i++ ) {
        queue.push(children[i]); // 队首元素的子元素进入队尾
      }
    }
  }
  return nodeList;
}

setState

积累

成年人的成长在于一次次的积累