ノードXから他のノードへのパスを、親を持つ与えられたjavascriptオブジェクトを使って計算する

Question

ノードT、U、V、X、W、Y、Zの7つのグラフがあるとします。私は計算する必要が上記オブジェクトを使用

parent of T is V 
parent of U is V 

：

Iは、ノードX

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

元からの最短パスを計算した後、各ノードの親を含むJavaScriptオブジェクトを持っています

ex：

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

JAVASCRIPTで、オブジェクト名パスへのパスを出力する単純なプログラムが必要です。

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 
}