Skip to content

Latest commit

 

History

History
219 lines (173 loc) · 6.84 KB

dfs.md

File metadata and controls

219 lines (173 loc) · 6.84 KB
Raw
title
深度优先遍历

React 算法之深度优先遍历

对于树或图结构的搜索(或遍历)来讲, 分为深度优先(DFS)和广度优先(BFS).

概念

深度优先遍历: DFS(英语:Depth-First-Search,DFS)是一种用于遍历或搜索树或图的算法.

来自 wiki 上的解释(更权威): 当节点v的所在边都己被探寻过, 搜索将回溯到发现节点v的那条边的起始节点. 这一过程一直进行到已发现从源节点可达的所有节点为止. 如果还存在未被发现的节点, 则选择其中一个作为源节点并重复以上过程, 整个进程反复进行直到所有节点都被访问为止.

实现方式

DFS 的主流实现方式有 2 种.

  1. 递归(简单粗暴)
  2. 利用栈存储遍历路径
function Node() {
  this.name = '';
  this.children = [];
}

function dfs(node) {
  console.log('探寻阶段: ', node.name);
  node.children.forEach(child => {
    dfs(child);
  });
  console.log('回溯阶段: ', node.name);
}
  1. 使用栈
function Node() {
  this.name = '';
  this.children = [];

  // 因为要分辨探寻阶段和回溯阶段, 所以必须要一个属性来记录是否已经访问过该节点
  // 如果不打印探寻和回溯, 就不需要此属性
  this.visited = false;
}

function dfs(node) {
  const stack = [];
  stack.push(node);
  // 栈顶元素还存在, 就继续循环
  while ((node = stack[stack.length - 1])) {
    if (node.visited) {
      console.log('回溯阶段: ', node.name);
      // 回溯完成, 弹出该元素
      stack.pop();
    } else {
      console.log('探寻阶段: ', node.name);
      node.visited = true;
      // 利用栈的先进后出的特性, 倒序将节点送入栈中
      for (let i = node.children.length - 1; i >= 0; i--) {
        stack.push(node.children[i]);
      }
    }
  }
}

React 当中的使用场景

深度优先遍历在react当中的使用非常典型, 最主要的使用时在ReactElement和fiber树的构造过程. 其次是在使用context时, 需要深度优先地查找消费context的节点.

ReactElement "树"的构造

ReactElement不能算是严格的树结构, 为了方便表述, 后文都称之为树.

在react-reconciler包中, ReactElement的构造过程实际上是嵌套在fiber树构造循环过程中的, 与fiber树的构造是相互交替进行的(在fiber 树构建章节中详细解读, 本节只介绍深度优先遍历的使用场景).

ReactElement树的构造, 实际上就是各级组件render之后的总和. 整个过程体现在reconciler工作循环之中.

源码位于ReactFiberWorkLoop.js中, 此处为了简明, 已经将源码中与 dfs 无关的旁支逻辑去掉.

function workLoopSync() {
  // 1. 最外层循环, 保证每一个节点都能遍历, 不会遗漏
  while (workInProgress !== null) {
    performUnitOfWork(workInProgress);
  }
}

function performUnitOfWork(unitOfWork: Fiber): void {
  const current = unitOfWork.alternate;
  let next;
  // 2. beginWork是向下探寻阶段
  next = beginWork(current, unitOfWork, subtreeRenderLanes);
  if (next === null) {
    // 3. completeUnitOfWork 是回溯阶段
    completeUnitOfWork(unitOfWork);
  } else {
    workInProgress = next;
  }
}

function completeUnitOfWork(unitOfWork: Fiber): void {
  let completedWork = unitOfWork;
  do {
    const current = completedWork.alternate;
    const returnFiber = completedWork.return;
    let next;
    // 3.1 回溯并处理节点
    next = completeWork(current, completedWork, subtreeRenderLanes);
    if (next !== null) {
      // 判断在处理节点的过程中, 是否派生出新的节点
      workInProgress = next;
      return;
    }
    const siblingFiber = completedWork.sibling;
    // 3.2 判断是否有旁支
    if (siblingFiber !== null) {
      workInProgress = siblingFiber;
      return;
    }
    // 3.3 没有旁支 继续回溯
    completedWork = returnFiber;
    workInProgress = completedWork;
  } while (completedWork !== null);
}

以上源码本质上是采用递归的方式进行 dfs, 假设有以下组件结构:

class App extends React.Component {
  render() {
    return (
      <div className="app">
        <header>header</header>
        <Content />
        <footer>footer</footer>
      </div>
    );
  }
}

class Content extends React.Component {
  render() {
    return (
      <React.Fragment>
        <p>1</p>
        <p>2</p>
        <p>3</p>
      </React.Fragment>
    );
  }
}

export default App;

则可以绘制出遍历路径如下:

注意:

  • ReactElement树是在大循环中的beginWork阶段"逐级"生成的.
  • "逐级"中的每一级是指一个class或function类型的组件, 每调用一次render或执行一次function调用, 就会生成一批ReactElement节点.
  • ReactElement树的构造, 实际上就是各级组件render之后的总和.

fiber 树的构造

在ReactElement的构造过程中, 同时伴随着fiber树的构造, fiber树同样也是在beginWork阶段生成的.

绘制出遍历路径如下:

查找 context 的消费节点

当context改变之后, 需要找出依赖该context的所有子节点(详细分析会在context原理章节深入解读), 这里同样也是一个DFS, 具体源码在ReactFiberNewContext.js.

将其主干逻辑剥离出来, 可以清晰的看出采用循环递归的方式进行遍历:

export function propagateContextChange(
  workInProgress: Fiber,
  context: ReactContext<mixed>,
  changedBits: number,
  renderLanes: Lanes,
): void {
  let fiber = workInProgress.child;
  while (fiber !== null) {
    let nextFiber;
    // Visit this fiber.
    const list = fiber.dependencies;
    if (list !== null) {
      // 匹配context等逻辑, 和dfs无关, 此处可以暂时忽略
      // ...
    } else {
      // 向下探寻
      nextFiber = fiber.child;
    }
    fiber = nextFiber;
  }
}

总结

由于react内部使用了ReactElement和fiber两大树形结构, 所以有不少关于节点访问的逻辑.

本节主要介绍了DFS的概念和它在react源码中的使用情况. 其中fiber树的DFS遍历, 涉及到的代码多, 分布广, 涵盖了reconciler阶段的大部分工作, 是reconciler阶段工作循环的核心流程.

除了DFS之外, 源码中还有很多逻辑都是查找树中的节点(如: 向上查找父节点等). 对树形结构的遍历在源码中的比例很高, 了解这些算法技巧能够更好的理解react源码.

参考资料

深度优先搜索