Нахождение всех возможных путей из одной точки в другую в дереве на JavaScript

Question

Хочу найти и вывести все возможные пути от А до D:

            graph = {'A': ['B', 'C'],
             'B': ['A', 'D'],
             'C': ['A', 'D'],
             'D': ['C', 'B']}
            function wid(graph, start, end) {
            let mas = [];
            mas.push(start);
            while (mas.length > 0) {
                  const cur = mas.shift();
                  if (!graph[cur]) {
                       graph[cur] = [];
                  }
                  if (graph[cur].includes(end)) {
                      return true;
                  }
                   else {
                      mas = [...mas, ...graph[cur]];
                   }
                }
              return false;
            }
           console.log(wid(graph, 'A', 'D'));

Как это сделать?

Answer 1

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

Эти пометки (visited и т.п.) хранились в глобальном массиве (или другой структуре данных), так что любая новая ветвь поиска не могла зайти в уже посещённые ветви.

А вот если делать эти пометки локальными - что нетрудно при рекурсивной реализации - то возможно будет найти один путь из начальной вершины в конечную, потом отойти на несколько уровней назад, и найти другой путь, и так далее.

Таким образом, достаточно передавать массив с пометками в качестве аргумента рекурсивной функции.

Пример на Python:

Adj = [[1,2,4],[0,3],[0,5],[1,4,6],[0,3,5],[2,4,6],[3,5]]

def AllPaths(V, Dst, Path):
    if V == Dst:
        print(Path)
    else:
        for W in Adj[V]:
            if not (W in Path):
                AllPaths(W, Dst, Path + [W])

AllPaths(0, 3, [0])

>>>
[0, 1, 3]
[0, 2, 5, 4, 3]
[0, 2, 5, 6, 3]
[0, 4, 3]
[0, 4, 5, 6, 3]

БЛОГ НА HUSL

Нахождение всех возможных путей из одной точки в другую в дереве на JavaScript

Ответы (1 шт):