所有可能的途径来达到向图中特定的节点 [英] All possible path to reach particular node in directed graph
问题描述
我在哪里路径存储在JSON数组就像一个有向图。它是在源和目的地的形式
瓦尔pathDirection = [{源代码:2,目标:3},
{源代码:3,目标:4},
{源:5,目标:4},
{源代码:2,目标:5},
{源代码:4,目标:6}]。
使用上面形成如下图所示的结构图。
我的问题是我不知道的出发点,我必须找到从任何节点达到6所有可能的路径
像上面的图不同的路径到达6
输出:
[4 - →6]
[3-→4 - →6]
[5-→4 - →6]
[2→5→4 - →6]
[2→3→4 - →6]
我曾尝试下面写算法中使用回溯其工作正常,但寻找一些最好的算法中找到。请提出任何其他可能的方式做同样的,我该如何优化下面PROGRAME。
// BackTrack的从终端节点目标6
VAR getAllSource =功能(destId){
变种sourceForsameDist = [];
pathDirection.forEach(函数(eachDirection){
如果(eachDirection.Destination == destId){
sourceForsameDist.push(eachDirection.Source);
}
});
返回sourceForsameDist;
};
变种diffPath = [];
VAR的init =功能(目的地){
VAR的sourceID = getAllSource(目标[destination.length - 1]);
如果(sourceId.length === 0){
diffPath.push(目标);
}
对于(VAR I = 0; I< sourceId.length;我++){
VAR副本= destination.slice(0);
copy.push(的sourceID [I]);
的init(复印件);
}
};
初始化([6]);
执行console.log(diffPath); // [[6,4,3,2],[6,4,5,2]]
我曾尝试使用回溯其工作正常,但想找找一些最好的算法中做的。
不过,我想对执行提出了一些建议:
- 请
diffPath
局部变量和返回
从它的的init
功能 - 如果您省略
如果(sourceId.length === 0)
条件,那么你会得到预期的输出,不仅从源头上的路径李> - 而不是在整个
pathDirection
在你getAllSource
功能循环,我会使用一个查找表在开始之前,穿越充满 - 改名
的init
来更有意义
I have a directed graph where paths are stored in JSON array like. It is in the form of source and destination .
Var pathDirection = [{"Source":2,"Destination":3},
{"Source":3,"Destination":4},
{"Source":5,"Destination":4},
{"Source":2,"Destination":5},
{"Source":4,"Destination":6}];
Using above it forms graph like below structure .
My problem is I don’t know the starting point and I have to find all possible path to reach 6 from any node
Like for above graph different path to reach 6 is
Output:
[4 ->6]
[3->4 ->6]
[5->4 ->6]
[2->5->4 ->6]
[2->3->4 ->6]
I have tried to write below algo using backtracking which is working fine but looking for some best algo to find. Please suggest any other possible way to do same and how can i optimize below programe.
// 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]]
I have tried to do using backtracking which is working fine but looking for some best algo to find.
I'd call it Depth-First-Search instead of backtracking, but yes the algorithm is fine.
However, I'd have some suggestions on the implementation:
- make
diffPath
a local variable andreturn
it from theinit
function - If you omit the
if(sourceId.length === 0)
condition then you will get the expected output, not only the the paths from the sources - instead of looping through the whole
pathDirection
s in yourgetAllSource
function, I'd use a lookup table that is filled before starting the traversal - rename
init
to something more meaningful
这篇关于所有可能的途径来达到向图中特定的节点的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!