javascript - 给定某些节点的所有可能路线，返回起始节点

Question

我目前正在研究一个小问题，该问题将输出访问所有节点并返回起始节点的所有可能组合。

我的数组中有三个节点["a", "b", "c"]所有可能的路线是

pairs = [ [ 'a', 'b' ],
  [ 'a', 'c' ],
  [ 'b', 'a' ],
  [ 'b', 'c' ],
  [ 'c', 'a' ],
  [ 'c', 'b' ] ];

我生成路由的函数是(__ 用于下划线库)

routesRecursive = function(pairs, currentNode, origin, result) {
  __.each(pairs, function(pair) {
    if (currentNode === __.first(pair)) {
      var currentRoute = pair;
      var nextNode = __.last(currentRoute);
      if (nextNode === origin) {
        result.push(pair);
      } else {
        result.push(currentRoute);
        routesRecursive(__.without(pairs, currentRoute), nextNode, origin, result); 
      }
    }
  });
  return result;
}
routesRecursive(pairs, "a", "a", [])

期望的输出是:

[
  [["a", "b"], ["b", "a"]],
  [["a", "b"], ["b", "c"], ["c", "a"]],
  [["a", "b"], ["b", "c"], ["c", "b"], ["b", "a"]],
  [["a", "c"], ["c", "a"]],
  [["a", "c"], ["c", "b"], ["b", "a"]],
  [["a", "c"], ["c", "b"], ["b", "c"], ["c", "a"]]
]

我的函数似乎无法产生所需的结果，有人有什么建议吗？

谢谢!

Answer 1

试试这个:

function paths({ graph = [], from, to }, path = []) {
    const linkedNodes = memoize(nodes.bind(null, graph));
    return explore(from, to);

    function explore(currNode, to, paths = []) {
        path.push(currNode);
        for (let linkedNode of linkedNodes(currNode)) {
            if (linkedNode === to) {
                let result = path.slice(); // copy values
                result.push(to);
                paths.push(result);
                continue;
            }
            // do not re-explore edges
            if (!hasEdgeBeenFollowedInPath({
                    edge: {
                        from: currNode,
                        to: linkedNode
                    },
                    path
                })) {                    
                explore(linkedNode, to, paths);
            }
        }
        path.pop(); // sub-graph fully explored            
        return paths;
    }
}

/** 
 * Get all nodes linked 
 * to from `node`.
 */
function nodes(graph, node) {
    return graph.reduce((p, c) => {
        (c[0] === node) && p.push(c[1]);
        return p;
    }, []);
}

/**
 * Has an edge been followed 
 * in the given path?
 */
function hasEdgeBeenFollowedInPath({ edge, path }) {
    var indices = allIndices(path, edge.from);
    return indices.some(i => path[i + 1] === edge.to);
}

/**
 * Utility to get all indices of 
 * values matching `val` in `arr`.
 */
function allIndices(arr, val) {
    var indices = [],
        i;
    for (i = 0; i < arr.length; i++) {
        if (arr[i] === val) {
            indices.push(i);
        }
    }
    return indices;
}

/**
 * Avoids recalculating linked 
 * nodes.
 */
function memoize(fn) {
    const cache = new Map();
    return function() {
        var key = JSON.stringify(arguments);
        var cached = cache.get(key);
        if (cached) {
            return cached;
        }
        cached = fn.apply(this, arguments)
        cache.set(key, cached);
        return cached;;
    };
}
const graph = [
    ['a', 'b'],
    ['a', 'c'],
    ['b', 'a'],
    ['b', 'c'],
    ['c', 'a'],
    ['c', 'b']
];
document.write(JSON.stringify(paths({
    graph,
    from: 'a',
    to: 'a'
})));