[Алгоритм] Поиск в ширину/в глубину, с которым сталкивается интерфейс

алгоритм
[Алгоритм] Поиск в ширину/в глубину, с которым сталкивается интерфейс

предисловие

Во время интервью или серфинга в техническом сообществе вы случайно увидите понятия поиска в глубину и поиска в ширину, На этот раз соответствующие знания используются в одном из требований проекта, поэтому я обобщу его здесь через теорию + практика один раз.

1. Пример

Следующая картинка может сравнить и понять разницу между ними:

优先搜索

Чтобы облегчить операцию позже, мы сначала определим набор параллельных узлов следующим образом, предполагая общий корневой узел:

节点

const root = [
  {
    id: '1',
    children: [
      {
        id: '1-1',
        children: [{ id: '1-1-1' }, { id: '1-1-2' }],
      },
      {
        id: '1-2',
        children: [{ id: '1-2-1' }, { id: '1-2-2' }],
      },
    ],
  },
  {
    id: '2',
    children: [
      {
        id: '2-1',
        children: [{ id: '2-1-1' }, { id: '2-1-2' }],
      },
      {
        id: '2-2',
        children: [{ id: '2-2-1' }, { id: '2-2-2' }],
      },
    ],
  },
  {
    id: '3',
    children: [
      {
        id: '3-1',
        children: [{ id: '3-1-1' }, { id: '3-1-2' }],
      },
      {
        id: '3-2',
        children: [{ id: '3-2-1' }, { id: '3-2-2' }],
      },
    ],
  },
];

const target = '2-2-2';

2. Поиск в глубину

Поиск в глубину (deep first search), как также видно из рисунка, начинается с корневого узла, ищет по глубине дерева, и ищет ветви как можно глубже. Когда ребро, в котором расположен узел, было найдено, вернитесь к предыдущему узлу, а затем выполните поиск оставшихся ребер.

Поиск в глубину использует структуру стека, последний вошел первым.

алгоритм:

js рекурсивная реализация и нерекурсивная реализация:

const depthFirstSearchWithRecursive = source => {
  const result = []; // 存放结果的数组
  // 递归方法
  const dfs = data => {
    // 遍历数组
    data.forEach(element => {
      // 将当前节点 id 存放进结果
      result.push(element.id);
      // 如果当前节点有子节点，则递归调用
      if (element.children && element.children.length > 0) {
        dfs(element.children);
      }
    });
  };
  // 开始搜索
  dfs(source);
  return result;
};

const depthFirstSearchWithoutRecursive = source => {
  const result = []; // 存放结果的数组
  // 当前栈内为全部数组
  const stack = JSON.parse(JSON.stringify(source));
  // 循环条件，栈不为空
  while (stack.length !== 0) {
    // 最上层节点出栈
    const node = stack.shift();
    // 存放节点
    result.push(node.id);
    // 如果该节点有子节点，将子节点存入栈中，继续下一次循环
    const len = node.children && node.children.length;
    for (let i = len - 1; i >= 0; i -= 1) {
      stack.unshift(node.children[i]);
    }
  }
  return result;
};

3. Поиск в ширину

Поиск в ширину (breadth first search), который также можно увидеть из рисунка, начинается с корневого узла и ведет поиск по ширине дерева, при посещении всех узлов алгоритм прерывается.

Поиск в ширину использует форму очереди «первым пришел — первым вышел».

js-реализация:

const breadthFirstSearch = source => {
  const result = []; // 存放结果的数组
  // 当前队列为全部数据
  const queue = JSON.parse(JSON.stringify(source));
  // 循环条件，队列不为空
  while (queue.length > 0) {
    // 第一个节点出队列
    const node = queue.shift();
    // 存放结果数组
    result.push(node.id);
    // 当前节点有子节点则将子节点存入队列，继续下一次的循环
    const len = node.children && node.children.length;
    for (let i = 0; i < len; i += 1) {
      queue.push(node.children[i]);
    }
  }
  return result;
};

4. Практическое применение

Практическое применение определенно больше, чем то, с которым я сталкивался, например, я буду использовать свой собственный опыт в качестве примера.

Требования следующие:

Можно создавать уровни организации, а под большим уровнем есть маленькие уровни, которые можно создавать бесконечно. При этом при редактировании должны быть перечислены все родительские уровни (компоненты дерева iview и каскада).

Проще говоря, это найти узел в дереве и вернуть путь к узлу.

tree

cascader

4.1 Поиск в глубину

алгоритм:

  1. Сначала поместите корневой узел в стек (в примере нет корневого узла, а параллельные узлы размещены напрямую);
  2. Возьмите первый узел из стека, сохраните и проверьте, является ли он целевым;
    • Если цель найдена, вернуть путь к хранилищу;
    • В противном случае поместите в стек непосредственных потомков текущего узла;
  3. Повторите шаг 2;
  4. Если нет прямых дочерних элементов, которые не были найдены, извлеките последний узел в узле хранения.
    • Если сохраненный узел пуст, определите, есть ли в стеке другие узлы, повторите шаг 2.
    • В противном случае завершите поиск и сообщите о результатах.
  5. Получить последний узел в узле хранения и открыть первый прямой дочерний узел;
  6. Если после удаления все еще есть прямой дочерний узел текущего последнего узла, повторите шаг 2 (используйте первый прямой дочерний узел текущего узла);
  7. Повторите шаг 2 (используя текущий узел);
// 深度优先搜索
const findPathByDepthFirstSearch = source => {
  const stack = JSON.parse(JSON.stringify(source));
  const result = [];
  const dfs = data => {
    // 保存当前节点
    // （在路口洒下面包屑）
    result.push(data);
    // 当前节点的值为真，则返回路径
    //（如果这个路口的终点是生门，通过记录的面包屑就找到了路径）
    if (data.id === target) {
      return result.map(r => r.id);
    }
    // 如果当前节点有子节点，则继续查找子节点
    //（如果这个路口后面还有分叉路口，就先去第一个分叉路口下的第一条路）
    if (data.children && data.children.length > 0) {
      return dfs(data.children[0]);
    }
    // 最后一个节点的值为假，弹出路径中的该节点
    //（最后一个路口是死路，清理最后一个路口的面包屑）
    result.pop();
    // 如果路径数组为空，则判断源节点是否还有待搜索的节点
    //（如果面包屑都清空了，也就是回到了原点，那就看看还有没有别的路口）
    if (result.length === 0) {
      return stack.length > 0 ? dfs(stack.shift()) : result;
    }
    // 获取路径中最后一个节点，是当前节点的父节点
    //（去撒有面包屑的最后一个路口看看，当前路口的面包屑已经在上面被清理了）
    const lastNode = result[result.length - 1];
    // 弹出路径中最后节点中的第一个子节点（前面已经查找失败了）
    //（当前路子不够野【在上面已经试过这条路，是死路】）
    lastNode.children.shift();
    // 查找最后一个有效节点的下一个子节点（前一个被 shift 了）
    //（如果这个路口下还有其他没尝试过的路，从第一条（实际是下一条了）开始尝试）
    if (lastNode.children.length > 0) {
      return dfs(lastNode.children[0]);
    }
    // 最后节点下的子节点全部尝试查找失败，返回上一个节点查找
    //（这个路口如果没有其他路了，清理面包屑且去上一个路口的第二条路看看【本条是第一条路，已经走过了】）
    return dfs(result.pop());
  };
  // 开始找路
  return dfs(stack.shift());
};

4.2 Поиск в ширину

алгоритм:

  1. Сначала поместите в очередь корневой узел (в примере нет корневого узла, а параллельные узлы размещаются напрямую);
  2. Возьмите первый узел из очереди и проверьте, является ли он целевым;
    • Если цель найдена, завершить поиск и рекурсивно найти родительское хранилище, возвращая путь
    • В противном случае добавьте все его непроверенные прямые дочерние элементы (требуется результат пути, установите родительский флаг для прямых дочерних элементов) в очередь
  3. Если очередь пуста, это означает, что были просмотрены все узлы и цели нет, и в конце поиска возвращается пустой результат;
  4. Повторите шаг два;

код показывает, как показано ниже:

// 广度优先搜索
const findPathByBreadthFirstSearch = source => {
  let result = [];
  let queue = JSON.parse(JSON.stringify(source));
  while (queue.length > 0) {
    // 遍历队列（队列会动态增加）
    //（从第一个路口开始试探）
    for (let i = 0; i < queue.length; i += 1) {
      // 获取当前队列的一项
      // （这是一个路口）
      const node = queue[i];
      // 判断节点是否为目标节点
      //（路口是不是生门？）
      if (node.id === target) {
        // 队列清空
        //（已经找到生门，不用再接着找了）
        queue = [];
        // 通过 parent 一层层查找路径
        //（从这个路口通过面包屑【parent】找归途，直到找到回家的路）
        return (function findParent(data) {
          result.unshift(data.id);
          if (data.parent) {
            return findParent(data.parent);
          }
          return result;
        })(node);
      }
      // 节点有子节点，设置子节点的 parent 为当前节点，推入队列
      //（这个路口下还有其他路，先记住这个这个路口下的路是属于现在这个路口的【parent】
      // 然后去下一个路口，按顺序来试）
      if (node.children && node.children.length > 0) {
        queue.push(
          ...node.children.map(leaf => {
            leaf.parent = node;
            return leaf;
          })
        );
      }
    }
  }
  return result;
};

Суммировать

Вообще говоря, поиск в глубину также можно использовать для поиска в ширину, С точки зрения мышления мозга, поиск в глубину больше соответствует когнитивному поведению людей. В то же время, когда узлы достаточно сложны, чтобы рассмотреть возможность использованияИтеративный поиск в глубину с углублением(неоднократно выполняя поиск в глубину с ограничением по глубине), временная сложность такая же, как и при поиске в ширину, а пространственная сложность намного выше.

Категории