Невозможно получить все маршруты от A до E в ориентированном графе

Question

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

let graph = {
    'A': ['B', 'D', 'E'],
    'B': ['C'],
    'C': ['D', 'E'],
    'D': ['C', 'E'],
    'E': ['B']
};

function search(start, end, graph) {
    
    let queue = [...graph[start]];
    let visited =  [];
    while (queue.length) {
      count = 1;
      let node = queue.shift();
      if (graph[node]){
          let answer = recursiveStep(node, end, graph, str = node, visit = new Set(), nodes = []);
          if (answer){
            visited.push(answer);
          }
      }
    }
    return visited;
}

function recursiveStep(start, end, graph, str, visit, nodes) {   
    if (end === start) {
        if (str.length <= 3 && !visit.has(str)) {
            visit.add(str)
            return str};
    }
    if (str.length > 3) return str = ""; 
    nodes.push(...graph[start])
    while (nodes.length) {
        start = nodes.shift();
        str += start
        return recursiveStep(start, end, graph, str, visit, nodes)
    }
    return visit
}


console.log(search('A', 'E', graph));

Вывод ['DCE', 'E'], однако, поскольку мне нужны все маршруты, меньшие или равные 3. Это должно быть: ['BCE',«DCE», «DE», «E»]. Код работает, если вы хотите скопировать и вставить его, используя узел. Может быть, есть ошибка, не слишком уверенная, но я также пытался сделать это многократно.

Answer 1

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

Затем проверяете, не достигнут ли конец, и повторяете следующий узел.

Или нажмитерезультат.

function search(start, end, graph) {
    function iter(node, visited) {
        graph[node].forEach(n => {
            if (visited.length > 2 || visited.includes(n)) return;
            if (n !== end) return iter(n, [...visited, n]);
            result.push([...visited, n].join(''));                
        });
    }
    
    var result = [];
    iter(start, []);
    return result;
}


let graph = { A: ['B', 'D', 'E'], B: ['C'], C: ['D', 'E'], D: ['C', 'E'], E: ['B'] };

console.log(search('A', 'E', graph));