这个解决方案怎么样,我认为它只适用于 DAG:有向无环图
function toGraph(arr){
d = {}
for (var e=0; e<arr.length; e++){
var edge = arr[e].split('-')
if(!d[edge[0]]){d[edge[0]]=[]}
if(!d[edge[1]]){d[edge[1]]=[]}
d[edge[0]].push(edge[1])
}
return d
}
function DFS(G,node,path,paths,visited){
visited[node] = true
path.push(node)
if (G[node].length==0 && path.length>1) paths.push('['+path.join('-')+']')
for (var s=0; s<G[node].length; s++){
successor = G[node][s]
if(!visited[successor]){
DFS(G,successor,path,paths,visited)
}
}
visited[node] = false
path.pop()
}
function go(){
var arr = ['1-2','1-6','2-6','2-3','1-4','1-5','6-7','4-7','7-8']
var paths = []
DFS(toGraph(arr),'1',[],paths,{})
return paths.toString()
}
当你打电话时go()
,你会得到以下输出
[1-2-6-7-8], [1-2-3], [1-6-7-8], [1-4-7-8], [1-5]