使用给定的 javascript 对象和父节点计算从节点 X 到其他节点的路径

Question

考虑有一个包含 7 个节点 T、U、V、X、W、Y、Z 的图。

我有一个 Javascript 对象，它在计算从节点 X 的最短路径后包含每个节点的父节点。

parents {"T":"V","U":"V","V":"X","W":"X","X":"X","Y":"X","Z":"X"}

例如：

parent of T is V
parent of U is V

使用上面的对象，我需要从 X 计算每个节点的路径。

例如：

X->X :  X
X->Y :  XY
X->Z :  XZ
X->T :  XVT
X->U :  XVU

所以我需要 JAVASCRIPT 中的一个简单程序，它将输出对象名称 path.[= 的路径15=]

ex:
path {"X":"X", "Y":"XY", "Z":"XZ", "T":"XVT", "U":"XVU", "W":"XW"}

如有任何帮助或建议，我们将不胜感激。

感谢阅读！

Answer 1

大体思路是使用dfs算法。这是非常基本的，唯一的事情就是找到你应该在每次递归调用时导航到的节点，这里是一些带有解释的代码：

let func = (parents) => {
   let ans = {}; // ans will contain all of our paths 
   let dfs = (X, path) => { // dfs function to run over tree
     ans[X] = path; // putting current path to current vertex
     let neighbours = [];
     Object.keys(parents).forEach(key => {
       if (parents[key] == X) { // looking for vertices where X is parent 
          neighbours.push(key);
       }
     });
     if (parents[X] != null) { // looking for parent of X
        neighbours.push(X);
     }
     neighbours.forEach(neighbour => { // iterating over all of the neighbour vetrices
       if (!ans[neighbour]) { // if it is not visited 
        dfs(neighbour, path + neighbour); // go into it with updated path
       }
     })
   };
   dfs("X", "X"); // run on initial node
   return ans; // don't forget to return calculated answer
}

使用给定的 javascript 对象和父节点计算从节点 X 到其他节点的路径

Calculate path from node X to other nodes using a given javascript object with parents

javascript

tree

jquery

dijkstra