freeCodeCamp/curriculum/challenges/ukrainian/10-coding-interview-prep/data-structures/depth-first-search.md

id, title, challengeType, forumTopicId, dashedName

id	title	challengeType	forumTopicId	dashedName
587d825d367417b2b2512c96	Пошук у глибину	1	301640	depth-first-search

--description--

Тут ми ознайомимося з алгоритмом обходу графу під назвою пошук у глибину, який є подібним до пошуку у ширину.

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

Коли пошук досягне кінця шляху, він повернеться до останнього вузла з невідвіданим ребром і продовжить пошук.

На анімації нижче наочно показано, яким чином працює цей алгоритм. Алгоритм починається з верхнього вузла і проходить по вузлах так, як пронумеровано в анімації.

Зверніть увагу: щоразу, коли даний алгоритм відвідує якийсь вузол, він не проходить по всіх сусідніх вузлах (в цьому полягає його відмінність від пошуку в ширину). Натомість він спочатку відвідує одну з сусідніх вершин і далі проходить вниз, допоки не відвідає всі вершини на цьому шляху.

Для реалізації цього алгоритму краще використати стек. Стек - це масив, в якому останній доданий елемент видаляється першим. Тобто це структура даних, яка працює за принципом Останній прийшов - перший пішов (англ. Last-In-First-Out (LIFO)). Стек допоможе при пошуку в глибину, адже (коли ми додаємо до стеку сусідні елементи) нам потрібно спочатку відвідати останніх доданих сусідів і вилучити їх зі стеку.

В простому випадку цей алгоритм виводить список вузлів, доступних з даного вузла. Таким чином, також краще відстежувати відвідані вузли.

--instructions--

Напишіть функцію dfs(), яка приймає неорієнтовану матрицю суміжності graph та мітку вузла root як параметри. Міткою вузла буде ціле значення вузла між 0 і n - 1, де n - загальна кількість вузлів у графі.

Ваша функція повинна виводити масив усіх вузлів, які можна досягти з root.

--hints--

Вхідний граф [[0, 1, 0, 0], [1, 0, 1, 0], [0, 1, 0, 1], [0, 0, 1, 0]] з початковим вузлом 1 повинен повертатися як масив з чисел 0, 1, 2 і 3.

assert.sameMembers(
  (function () {
    var graph = [
      [0, 1, 0, 0],
      [1, 0, 1, 0],
      [0, 1, 0, 1],
      [0, 0, 1, 0]
    ];
    return dfs(graph, 1);
  })(),
  [0, 1, 2, 3]
);

Вхідний граф [[0, 1, 0, 0], [1, 0, 1, 0], [0, 1, 0, 1], [0, 0, 1, 0]] з початковим вузлом 1 повинен повертатися як масив з чотирьох елементів.

assert(
  (function () {
    var graph = [
      [0, 1, 0, 0],
      [1, 0, 1, 0],
      [0, 1, 0, 1],
      [0, 0, 1, 0]
    ];
    return dfs(graph, 1);
  })().length === 4
);

Вхідний граф [[0, 1, 0, 0], [1, 0, 1, 0], [0, 1, 0, 0], [0, 0, 0, 0]] з початковим вузлом 3 повинен повертатися як масив з числом 3.

assert.sameMembers(
  (function () {
    var graph = [
      [0, 1, 0, 0],
      [1, 0, 1, 0],
      [0, 1, 0, 0],
      [0, 0, 0, 0]
    ];
    return dfs(graph, 3);
  })(),
  [3]
);

Вхідний граф [[0, 1, 0, 0], [1, 0, 1, 0], [0, 1, 0, 0], [0, 0, 0, 0]] з початковим вузлом 3 повинен повертатися як масив з одним елементом.

assert(
  (function () {
    var graph = [
      [0, 1, 0, 0],
      [1, 0, 1, 0],
      [0, 1, 0, 0],
      [0, 0, 0, 0]
    ];
    return dfs(graph, 3);
  })().length === 1
);

Вхідний граф[[0, 1, 0, 0], [1, 0, 0, 0], [0, 0, 0, 1], [0, 0, 1, 0]] з початковим вузлом 3 повинен повертатися як масив з чисел 2 і 3.

assert.sameMembers(
  (function () {
    var graph = [
      [0, 1, 0, 0],
      [1, 0, 0, 0],
      [0, 0, 0, 1],
      [0, 0, 1, 0]
    ];
    return dfs(graph, 3);
  })(),
  [2, 3]
);

Вхідний граф [[0, 1, 0, 0], [1, 0, 0, 0], [0, 0, 0, 1], [0, 0, 1, 0]] з початковим вузлом 3 повинен повертатися як масив з двох елементів.

assert(
  (function () {
    var graph = [
      [0, 1, 0, 0],
      [1, 0, 0, 0],
      [0, 0, 0, 1],
      [0, 0, 1, 0]
    ];
    return dfs(graph, 3);
  })().length === 2
);

Вхідний граф [[0, 1, 0, 0], [1, 0, 0, 0], [0, 0, 0, 1], [0, 0, 1, 0]] з початковим вузлом 0 повинен повертатися як масив з чисел 0 і 1.

assert.sameMembers(
  (function () {
    var graph = [
      [0, 1, 0, 0],
      [1, 0, 0, 0],
      [0, 0, 0, 1],
      [0, 0, 1, 0]
    ];
    return dfs(graph, 0);
  })(),
  [0, 1]
);

Вхідний граф [[0, 1, 0, 0], [1, 0, 0, 0], [0, 0, 0, 1], [0, 0, 1, 0]] з початковим вузлом 0 повинен повертатися як масив з двох елементів.

assert(
  (function () {
    var graph = [
      [0, 1, 0, 0],
      [1, 0, 0, 0],
      [0, 0, 0, 1],
      [0, 0, 1, 0]
    ];
    return dfs(graph, 0);
  })().length === 2
);

--seed--

--seed-contents--

function dfs(graph, root) {

}

var exDFSGraph = [
  [0, 1, 0, 0],
  [1, 0, 1, 0],
  [0, 1, 0, 1],
  [0, 0, 1, 0]
];
console.log(dfs(exDFSGraph, 3));

--solutions--

function dfs(graph, root) {
    var stack = [];
    var tempV;
    var visited = [];
    var tempVNeighbors = [];
    stack.push(root);
    while (stack.length > 0) {
        tempV = stack.pop();
        if (visited.indexOf(tempV) == -1) {
            visited.push(tempV);
            tempVNeighbors = graph[tempV];
            for (var i = 0; i < tempVNeighbors.length; i++) {
                if (tempVNeighbors[i] == 1) {
                    stack.push(i);
                }
            }
        }
    }
    return visited;
}