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

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

Как только вы посетили новую вершину, приостановите исследование текущей вершины и начните исследовать новую вершину.

Стек — это структура данных, используемая для этого обхода.

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

Сначала мы начнем с 1 и изучим 2, затем изучим 5, а затем 9. Когда мы изучим всех дочерних элементов 2, мы вернемся к 3. Затем из 3 мы посетим 6 и затем 10, и как только мы исследуем 10, мы вернемся к 3 и исследуем 7. Как только мы посетим все вершины 3, мы перейдем к 4 и посетим 8. Таким образом, мы исследуем все вершины в метод обхода предварительного заказа.

Код Sudo для подхода в глубину:

- start from the root element(it can be any)
- push the root in stack.
- Explore its child. (check if visited or not)
- if not visited, push to stack, and repeat the process until we explore all the 
vertices.
- if all nodes are processed, get value from stack and check for vertices that are not visited.

Давайте разберемся с работой этого неориентированного графа:

Матрица смежности для этого графа будет:

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

Во-первых, давайте создадим функцию для проверки существования непосещенной вершины для нашей текущей вершины.

/**
 * Function to check if any unvisited neighour vertex exist for current vertex
 * @param {*} currentNode , current node(vertex) that is being processed
 * @param {*} graph , graph, the adjacency matrix representation
 * @param {*} visitedNodes , Hashmap for vertex that are already been visited
 * @returns
 */
const findUnVisitedNode = (currentNode, graph, visitedNodes) => {
  const currentConnectedNodes = graph[currentNode]; //current connected vertex for this current vertex
  let neighborIdx = -1; // making it initial to -1, as no vertex is unvisited
  currentConnectedNodes.forEach((element, idx) => {
    // finding the first neighour unvisited vertex
    if (element == 1 && !visitedNodes[idx] && neighborIdx == -1) {
      neighborIdx = idx;
    }
  });
  return neighborIdx;
};

Теперь давайте создадим наш алгоритм для посещения всех вершин и вычисления расстояния между ними.

/**
 * Traversing through the graph
 * @param {Array} graph , graph matrix
 * @param {Number} rootNode , root node to start from
 */
const dfs = (graph, rootNode) => {
  // storing distance to the root node
  let nodeDistance = {};
  // start all distance from infinity
  for (let i = 0; i < graph.length; i++) {
    nodeDistance[i] = Infinity;
  }

  // distance from root node to root node is 0
  nodeDistance[rootNode] = 0;

  // creating a stack to keep track of nodes to visit later
  let stack = [rootNode];

  // setting the current vertex as visited as we don;t want to create a loop around it
  let visitedNodes = { [rootNode]: true };

  // iterate while we have vertex in stack
  while (stack.length) {
    // taking the current value in the stack that needs to be processed
    const currentNode = stack.pop();
    // checking if unvisited nodes are there or not
    const unvisitedNode = findUnVisitedNode(currentNode, graph, visitedNodes);
    // checking is any unvisited vertex exist for this current vertex or not
    if (unvisitedNode >= 0) {
      if (!visitedNodes[unvisitedNode]) {
        // value is not set as per now
        if (nodeDistance[unvisitedNode] == Infinity)
          nodeDistance[unvisitedNode] = nodeDistance[currentNode] + 1;
        visitedNodes[unvisitedNode] = true;
        // if a vertex is unvisited then we need to push the current vertex as well
        // as the next vertex that we need to explore
        stack.push(...[currentNode, unvisitedNode]);
      }
    } else {
      // if all vertices are visited then we don;t have to add any value in stack
      visitedNodes[unvisitedNode] = true;
    }
  }

  return nodeDistance;
};

давайте вызовем нашу функцию для выполнения

const newdfsGraph = [
  [0, 1, 1, 0, 0],
  [1, 0, 0, 1, 0],
  [1, 0, 0, 1, 1],
  [0, 1, 1, 0, 0],
  [0, 0, 1, 0, 0],
];

console.log(dfs(newdfsGraph, 1));

DFS сначала исследует глубину одной вершины, а затем переходит к следующей вершине.

Следите за новостями. Если вы впервые здесь, загляните в наш блог Алгоритмы с Javascript, мы расскажем о нескольких наиболее часто используемых алгоритмах.

В следующем блоге мы рассмотрим алгоритмы Дейкстры (поиск пути из одного источника).