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"
},
]

我需要编写一个javascript函数，给定一个起点（例如“B”），它将以最接近起点优先级的方式遍历图形。例如对于 B，它会得到孩子 D、F，然后是根，然后是兄弟 B、C，然后是孙子 G，然后是 B 和 C 的孩子，依此类推。

即使只有算法也可以

PS：我知道我可以在那里使用dijkstra，但我真的不知道如何

4

2 回答 2

1

例如，您可以在此处使用实现的广度优先搜索。如果树中的边具有与其相关的权重，则需要使用 Dijkstra 算法。

由于您没有将父项保留在节点对象中，因此您需要添加一个预处理步骤以将父字段添加到所有节点。这是必需的，以便在您开始时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 回答