javascript - 到达有向图中特定节点的所有可能路径

Question

我有一个有向图，其中路径存储在 JSON 数组中。它以源和目标的形式。

Var pathDirection =  [{"Source":2,"Destination":3},
{"Source":3,"Destination":4},
{"Source":5,"Destination":4},
{"Source":2,"Destination":5},
{"Source":4,"Destination":6}];

使用上面它形成如下结构的图形。

我的问题是我不知道起点，我必须找到从任何节点到达 6 的所有可能路径

像上图一样，达到 6 的不同路径是

输出:

    [4 ->6]
    [3->4 ->6]
    [5->4 ->6]
    [2->5->4 ->6]
    [2->3->4 ->6]

我尝试使用回溯法编写下面的算法，它工作正常，但正在寻找一些最好的算法。请建议任何其他可能的方法来做同样的事情，以及我如何优化下面的程序。

// BackTrack From End Node Destination 6

var getAllSource = function(destId){
    var sourceForsameDist = [];
    pathDirection.forEach(function(eachDirection){
      if(eachDirection.Destination == destId){
        sourceForsameDist.push(eachDirection.Source);
      }
  });
        return sourceForsameDist;
};

var diffPath = [];

var init = function(destination){
   var sourceId =  getAllSource(destination[destination.length - 1]);
    if(sourceId.length === 0){
      diffPath.push(destination);

    }
   for(var i=0;i<sourceId.length;i++){
     var copy  = destination.slice(0);
     copy.push(sourceId[i]);
     init(copy);
   }

};

init([6]);

console.log(diffPath);  // [[6,4,3,2],[6,4,5,2]]

Answer 1

I have tried to do using backtracking which is working fine but looking for some best algo to find.

我称之为 Depth-First-Search而不是 backtracking ，但是是的，算法很好。

但是，我对实现有一些建议:

• 使 diffPath 成为局部变量并从 init 函数返回它
• 如果您省略 if(sourceId.length === 0) 条件，那么您将获得预期的输出，而不仅仅是来自源的路径
• 我不会在 getAllSource 函数中遍历整个 pathDirection，而是使用在开始遍历之前填充的查找表
• 将 init 重命名为更有意义的名称