從網絡節點集

計算路徑我具有由限定的一組節點的連接的數組：從網絡節點集

var arr = ['1-2','1-6','2-6','2-3','1-4','1-5','6-7','4-7','7-8'];

1-2意味着節點1連接到節點2，依此類推。你可以看到有多個連接。

如果正確操作，你可以看到各種獨特的路徑，例如1-2-6-7-8，1-5等我想計算的路徑爲：

path = ['1-2-6-7-8','1-6-7-8','1-2-3','1-4-7-8','1-5']

我已經做了通過另一組檢查每個集合，但我認爲我的代碼太長，並且執行不好。什麼是獲得路徑數組的最佳途徑。（路徑在葉節點結束）

謝謝。

enter image description here

來源

2012-10-03 Pujan Srivastava

考慮將這些「連接」存儲在字符串之外的結構中。它將使與他們合作更容易。 – Brad

謝謝@Brad我會嘗試這種方式。 –

這個怎麼樣的解決方案，我認爲它只能與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]

來源

2012-10-03 06:46:42 user1406062

謝謝，這是一個不錯的緊湊解決方案。 –

從網絡節點集

回答

相關問題