1

次のようなグラフがあります。

root : {
    nodeType : "root",
    children: [
    "A",
    "B",
    "C"
    ]
}
nodes : [
"A": {
    nodeType : "node",
    children: [
    "D",
    "E"
    ]
},
"B": {
    nodeType : "node",
    children: [
    "D",
    "F"
    ]
},
"C": {
    nodeType : "leaf"
},
"D": {
    nodeType : "node",
    children: [
    "G"
    ]
},
"E": {
    nodeType : "leaf"
},
"F": {
    nodeType : "leaf"
},
"G": {
    nodeType : "leaf"
},
]

開始点（たとえば「B」）を指定すると、開始点に最も近い優先順位でグラフをトラバースするJavaScript関数を作成する必要があります。たとえば、B の場合、子 D、F、ルート、兄弟 B、C、孫 G、B と C の子などを取得します。

アルゴリズムさえあればいい

PS: ダイクストラを使用できることは知っていますが、その方法がわかりません。

4

2 に答える 2

1

たとえばここで実装された幅優先検索を使用できます。ツリーのエッジに重みが関連付けられている場合、ダイクストラのアルゴリズムが必要になります。

親をノード オブジェクトに保持しないため、親フィールドをすべてのノードに追加する前処理ステップを追加する必要があります。これは、開始時Bにルートにアクセスする必要があることを知るために必要です。これは、単純なトラバーサルを使用して実行できます。

幅優先検索では、アクセスする必要があるノードがキューに保持されます。新しいノードがキューの最後に追加されます。アルゴリズムは、キューの先頭からアクセスする新しいノードを選択します。

ただし、ノードの再リストが許可されている場合、キューが非常に大きくなる可能性があるため、注意してください。

于 2014-04-09T10:31:29.950 に答える
0

幅優先アルゴリズムの使用に関するcyonのアドバイスのおかげで、私はこれを思いつきました( http://java.dzone.com/articles/algorithm-week-graph-breadthに基づく):

var graph = {
    A : [B, C],
    B : [A, D],
    C : [A, D],
    D : [A, C ,E],
    E : [B, F],
    F : [E]
};

function init (visited, graph) 
{
    for (var key in graph) {
       var vertex = graph[key];
        visited[key] = false;
    }
}

function breadthFirst (graph, start, visited)
{
    // Create an empty queue
    var queue = [];

    // Initially enqueue only the starting vertex
    queue.push(start);

    //Set the starting vertex to visited
    visited[start] = true;

    //Add it to the result
    result.push( start );

    //While there is still remaining vertexes in queue
    while (queue.length > 0) {

       //Remove first vertex from queue and save it in "t"
       var currentVertexID = queue.shift();

       //For each key in graph at "t"
       var currentVertex = graph[currentVertexID];
       for (var key in currentVertex) {

       var target = currentVertex[key];

            //If it has not been visited yet
            if (!visited[target]) {

                //Mark it as visited
                visited[target] = true;

                //Add it to queue
                queue.push(target);

                //Save it in result
                result.push(target);
                //console.log(result);
            }
        }
    }
}

var result = [];
var visited = [];
init(visited, graph);
breadthFirst(graph, 2, visited);    
console.log(result);

また、ルートが分離していて、グラフ内に親から子への関係のみがあったため (ツリーから移行したため)、幅を最初に使用する前に完全な関係マトリックスを作成する必要がありました (親を検索できるようにするため)。

ツリーで最初に幅を使用するための前処理に役立つ可能性があるため、投稿します

generateNodesAdjacencyMatrix : function(){
            var adjacencyMatrix = {};
            function recursiveFindNestedAndSaveLinks(parentKey, childrenKeys){
                //Add the links to parent pointing to his children
                if(!_.isArray(adjacencyMatrix[parentKey])){
                    adjacencyMatrix[parentKey] = [];
                }
                adjacencyMatrix[parentKey] = adjacencyMatrix[parentKey].concat(childrenKeys);

                //For each children
                _.each(childrenKeys, function (childKey){
                    //Add a link to parent
                    if(!_.isArray(adjacencyMatrix[childKey])){
                        adjacencyMatrix[childKey] = [];
                    }
                    adjacencyMatrix[childKey].push(parentKey);

                    //If it has children as well, do recursive on him
                    var child = childs[childKey];
                    if(!_.isUndefined(child) && !_.isUndefined(child.children)){
                        recursiveFindNestedAndSaveLinks(childKey, child.children);
                    }
                }, this);
            }
            recursiveFindNestedAndSaveLinks('root', root.children);
            return adjacencyMatrix;
        },
于 2014-04-09T17:41:46.823 に答える