title: 深度优先遍历

React 算法之深度优先遍历

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

概念

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

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

实现方式

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

  1. 递归(简单粗暴)
  2. 利用栈存储遍历路径
  1. function Node() {
  2.   this.name = '';
  3.   this.children = [];
  4. }
  6. function dfs(node) {
  7.   console.log('探寻阶段: ', node.name);
  8.   node.children.forEach(child => {
  9.     dfs(child);
  10.   });
  11.   console.log('回溯阶段: ', node.name);
  12. }
  1. 使用栈
  1. function Node() {
  2.   this.name = '';
  3.   this.children = [];
  5.   // 因为要分辨探寻阶段和回溯阶段, 所以必须要一个属性来记录是否已经访问过该节点
  6.   // 如果不打印探寻和回溯, 就不需要此属性
  7.   this.visited = false;
  8. }
  10. function dfs(node) {
  11.   const stack = [];
  12.   stack.push(node);
  13.   // 栈顶元素还存在, 就继续循环
  14.   while ((node = stack[stack.length - 1])) {
  15.     if (node.visited) {
  16.       console.log('回溯阶段: ', node.name);
  17.       // 回溯完成, 弹出该元素
  18.       stack.pop();
  19.     } else {
  20.       console.log('探寻阶段: ', node.name);
  21.       node.visited = true;
  22.       // 利用栈的先进后出的特性, 倒序将节点送入栈中
  23.       for (let i = node.children.length - 1; i >= 0; i--) {
  24.         stack.push(node.children[i]);
  25.       }
  26.     }
  27.   }
  28. }

React 当中的使用场景

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

ReactElement “树”的构造

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

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

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

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

  1. function workLoopSync() {
  2.   // 1. 最外层循环, 保证每一个节点都能遍历, 不会遗漏
  3.   while (workInProgress !== null) {
  4.     performUnitOfWork(workInProgress);
  5.   }
  6. }
  8. function performUnitOfWork(unitOfWork: Fiber): void {
  9.   const current = unitOfWork.alternate;
  10.   let next;
  11.   // 2. beginWork是向下探寻阶段
  12.   next = beginWork(current, unitOfWork, subtreeRenderLanes);
  13.   if (next === null) {
  14.     // 3. completeUnitOfWork 是回溯阶段
  15.     completeUnitOfWork(unitOfWork);
  16.   } else {
  17.     workInProgress = next;
  18.   }
  19. }
  21. function completeUnitOfWork(unitOfWork: Fiber): void {
  22.   let completedWork = unitOfWork;
  23.   do {
  24.     const current = completedWork.alternate;
  25.     const returnFiber = completedWork.return;
  26.     let next;
  27.     // 3.1 回溯并处理节点
  28.     next = completeWork(current, completedWork, subtreeRenderLanes);
  29.     if (next !== null) {
  30.       // 判断在处理节点的过程中, 是否派生出新的节点
  31.       workInProgress = next;
  32.       return;
  33.     }
  34.     const siblingFiber = completedWork.sibling;
  35.     // 3.2 判断是否有旁支
  36.     if (siblingFiber !== null) {
  37.       workInProgress = siblingFiber;
  38.       return;
  39.     }
  40.     // 3.3 没有旁支 继续回溯
  41.     completedWork = returnFiber;
  42.     workInProgress = completedWork;
  43.   } while (completedWork !== null);
  44. }

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

  1. class App extends React.Component {
  2.   render() {
  3.     return (
  4.       <div className="app">
  5.         <header>header</header>
  6.         <Content />
  7.         <footer>footer</footer>
  8.       </div>
  9.     );
  10.   }
  11. }
  13. class Content extends React.Component {
  14.   render() {
  15.     return (
  16.       <React.Fragment>
  17.         <p>1</p>
  18.         <p>2</p>
  19.         <p>3</p>
  20.       </React.Fragment>
  21.     );
  22.   }
  23. }
  25. export default App;

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

React 算法之深度优先遍历 - 图1

注意:

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

fiber 树的构造

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

绘制出遍历路径如下:

React 算法之深度优先遍历 - 图2

查找 context 的消费节点

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

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

  1. export function propagateContextChange(
  2.   workInProgress: Fiber,
  3.   context: ReactContext<mixed>,
  4.   changedBits: number,
  5.   renderLanes: Lanes,
  6. ): void {
  7.   let fiber = workInProgress.child;
  8.   while (fiber !== null) {
  9.     let nextFiber;
  10.     // Visit this fiber.
  11.     const list = fiber.dependencies;
  12.     if (list !== null) {
  13.       // 匹配context等逻辑, 和dfs无关, 此处可以暂时忽略
  14.       // ...
  15.     } else {
  16.       // 向下探寻
  17.       nextFiber = fiber.child;
  18.     }
  19.     fiber = nextFiber;
  20.   }
  21. }

总结

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

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

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

参考资料

深度优先搜索