1

我无法弄清楚以下问题。在第 1 点我可以到第 2 点或第 5 点。从点到我可以到第 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);
    }
}
4

4 回答 4

2

我在下面放了一个解决方案，但如果你不想剧透就不要看了！它只处理图中没有循环的情况。

一些没有给出答案的提示：我建议在你的递归函数中，你在第二个参数中跟踪到目前为止的整个路径，而不仅仅是当前位置，否则你最终会得到一个访问过的位置列表，但是你怎么知道把你带到每一个的路径？其次，在 Javascript 中，使用构造遍历数组并不是一种好的做法for ... in，因此您可以使用从 0 到数组长度的常规 for 循环。第三，你会想在某个时候打印出构建的路径，但你不想在每一步都这样做：相反，你想在路径完成时打印出来；也就是说，当从当前位置没有更多地方可去时。最后，我替换document.write为console.log，因为我相信document.write每次打印时都会覆盖文档内容。

var a = [];
a[1]=[2,5];
a[2]=[3,4];
a[5]=[6,7];
a[7]=[8,9];

trytoloop(a,[1]);

function trytoloop(a,path){
  var last = path[path.length - 1];
  var next_hops = a[last];
  // if there could be cycles, you might want to check that next_hops doesn't
  // contain any already visited locations
  if (next_hops) {
    for (var i = 0; i < next_hops.length; i++) {
      var new_path = path.concat([next_hops[i]]);
      trytoloop(a, new_path);
    }
  } else {
    console.log(path);
  }
}
于 2012-12-09T19:51:48.933 回答
2

您没有跟踪到目前为止已建立的部分路径。不过，数组的想法似乎很好。这是一个带有一些更有意义名称的工作版本：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(","));
}
于 2012-12-09T19:51:55.277 回答
1

这是我的解决方案：小提琴

最终输出到console，您可以在此处更改初始节点console.log(getPaths(1));（根据您的要求从节点 1 开始）。

于 2012-12-09T20:09:31.450 回答
1

我还没有尝试过，但是在我脑海中，您可以尝试以下方法：

// use an object, and set the numbers as keys and the values as the child options
var a = {};
a[1] = {2:{3:{},4:{}},5:{6:{},7:{8:{9:{}}}}};

(function trytoloop(obj,num,str){
    if(str.length>0) str += ',';
    str += num
    if(Object.keys(obj).length==0) document.writeln(str+'<br />');
    else for(var key in obj) trytoloop(obj[key],key,str);
})(a[1],1,'');
于 2012-12-09T20:00:55.707 回答