javascript映射所有路径

Question

我无法弄清楚以下问题。在第 1 点我可以去第 2 点或第 5 点。从第 1 点到第 3 点或第 4 点。从第 5 点我可以去第 6 点或第 7 点。从第 7 点到第 9 点只有一条路。我想计算所有完整路径。我不是在寻找最快的路线或任何东西。我需要所有的路径，以便我可以轻松地遵循它们。

我有两个问题:

1. 我不确定我是否使用正确的方式来“存储”选项 (a[1]=[2,5])。这样可以吗？还有更好的方法吗？

2. 我不确定如何解决这个问题。谁能给我一个线索？我希望我在寻找正确的方向:-)

路径:

  1 ->2 ->3
        ->4
    ->5 ->6
        ->7 ->8 ->9

以及期望的结果:

 1,2,3
 1,2,4
 1,5,6
 1,5,7,8,9

我尝试用 javascript 解决这个问题

// this doesn't do what I need 
var a = [];
a[1]=[2,5];    
a[2]=[3,4];
a[5]=[6,7];
a[7]=[8];
a[8]=[9];

trytoloop(a,1);

function trytoloop(a,key){
    if(a[key]){
         for (var y in a[key]){
                document.write(key);

                trytoloop(a,a[key][y]);
         }
    } else {
        document.write(key);
    }
}

Answer 1

您不会跟踪到目前为止已经建立的部分路径。不过，数组的想法似乎不错。这是一个工作版本，其中包含一些更有意义的名称:http://jsfiddle.net/YkH5b/ .

// A cleaner way of defining the next keys
var nextKeysMap = {
    1: [2, 5],    
    2: [3, 4],
    5: [6, 7],
    7: [8],
    8: [9]
};

var fullPaths = [];
generateFullPaths([1], 1);  // start off with partial path [1] and thus at key 1

function generateFullPaths(partialPath, currentKey) {
    if(currentKey in nextKeysMap) {  // can we go further?
        var nextKeys = nextKeysMap[currentKey];  // all possible next keys
        for (var i = 0; i < nextKeys.length; i++) {  // loop over them
            var nextKey = nextKeys[i];
            // append the current key, and build the path further
            generateFullPaths(partialPath.concat(nextKey), nextKey);
         }
    } else {  // we cannot go further, so this is a full path
        fullPaths.push(partialPath);
    }
}

for(var i = 0; i < fullPaths.length; i++) {
    console.log(fullPaths[i].join(","));
}