JavaScript - 图遍历 - 从起始节点按顺序(最接近的第一个)获取节点

Question

我有一个看起来像这样的图表:

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，它会得到 child D、F，然后是 root，然后是 sibling B、C，然后是孙子 G，然后是 B 和 C 的 child 等等。

有算法就好了

PS:我知道我可以在那里使用 dijkstra，但我真的不知道怎么做

Answer 1

您可以使用 Breadth-first search例如实现 here .如果树中的边具有与之关联的权重，则需要 Dijkstra 算法。

由于您没有在节点对象中保留父级，因此您需要添加一个预处理步骤以将父级字段添加到所有节点。这是必需的，以便在 B 开始时您知道要访问根目录。这可以使用简单的遍历来完成。

广度优先搜索将您需要访问的节点保持在队列中。新节点被添加到队列的末尾。该算法从队列的前面挑选要访问的新节点。

不过要小心，因为如果允许重新访问节点，队列会变得非常大。