Поиск в глубину просто говорит, что после того, как вы посетили вершину, начните исследовать ее дочерние узлы и дочерние узлы до тех пор, пока не останется узла для исследования этой вершины, а затем перейдите к следующей вершине.
Поиск в глубину также известен как предварительный обход.
Как только вы посетили новую вершину, приостановите исследование текущей вершины и начните исследовать новую вершину.
Стек — это структура данных, используемая для этого обхода.
Давайте возьмем пример дерева ниже и попробуем понять, как работает поиск в глубину. мы начнем исследовать дерево с узла 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, мы расскажем о нескольких наиболее часто используемых алгоритмах.
В следующем блоге мы рассмотрим алгоритмы Дейкстры (поиск пути из одного источника).