1

次のように定義されたノード接続のセットの配列があります。

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']

各セットを別のセットでチェックしてみましたが、コードが長すぎてうまく機能しないと思います。パス配列を取得するための最良の方法は何ですか。（パスはリーフノードで終了します）

ありがとう。

ここに画像の説明を入力してください

4

1 に答える 1

1

このソリューションはどうでしょうか。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-03T06:46:42.950 に答える