如何遍歷一個節點有多個父節點並且總結值的圖？

Question

我從一個JSON出口接收到該數據：

nodes = [ 
    {id:1,data:29,parentOf:[]}, 
    {id:2,data:31,parentOf:[1,8,7]}, 
    {id:3,data:41,parentOf:[2,1]}, 
    {id:4,data:89,parentOf:[3,2,1]}, 
    {id:5,data:71,parentOf:[4,3,2,1,9,2,8,7]}, 
    {id:6,data:11,parentOf:[5,4,3,2,1]}, 
    {id:7,data:59,parentOf:[]}, 
    {id:8,data:43,parentOf:[7]}, 
    {id:9,data:97,parentOf:[2,8,7]} 
] 

這是從一個圖，其中所涉及的節點可以具有零對或多個父母的數據結構。該圖已被平放以輸出到節點陣列。 現在，我需要彙總數據的值字段。

我該如何遍歷這個圖來獲得每個節點的總數據？

編輯：用於提供必像的例子中，最終的結果如下：

[ 
    {id:1,sum:29}, 
    {id:2,sum:162}, // 31+102+29 
    {id:3,sum:203}, // 41+162 
    {id:4,sum:292}, // 89+203 
    {id:5,sum:622}, // 71+292+259 
    {id:6,sum:633}, // 11+622 
    {id:7,sum:59}, 
    {id:8,sum:102}, // 43+59 
    {id:9,sum:259} // 97+162 
] 

編輯2：這是從數據結構的上方，由得到的曲線圖的圖由我：

我現在看到，在節點的parentOf數組中，有一些冗餘信息。

儘管提供的示例只有沒有父母的節點（id：6），但我正在尋找解決方案來處理正常情況，其中沒有父母的節點多於一個。所以我認爲圖遍歷應該從葉節點開始，即id：1和id：7。

非常感謝非遞歸方法（如果可能的話）。

Answer 1

是什麼讓這個問題很難，就是parentOf列表有時不僅包含ID直接孩子值，但較偏遠的後裔也（部分）。所以真正的圖形不是直接顯而易見的。

例如，樣本數據列出了節點9作爲節點2,8和7的父節點。然而，圖像顯示，只有2個是9的直接子節點，而8和7是更遠的後代。節點1，這也是爲9的後代，沒有在節點9.

的parentOf屬性中列出其中的信息是真正直接子可以如它被賦予從數據推導出，但它需要一些工作。然而，這些信息需要能夠正確計算總和。

請注意，由於這種冗餘輸入的結果，不可能在圖中定義一個三角形。假設節點A具有節點B和C作爲子節點，並且節點B具有節點C作爲子節點：這樣的三角形將不能在上述數據結構中編碼，因爲A和C之間的鏈接將被視爲冗餘的「孫子」鏈接。

在我在這裏提出的解決方案中，我使用Set來記錄後代和直接的孩子，因爲這樣可以比數組快。

我還創建了一個Map用於使節點可以通過它們的ID訪問。同樣，這是出於性能原因。

在圖形中檢測到循環時，將拋出異常。

按照要求，該算法不依賴於遞歸。

下面是代碼：

function sumTree(nodes) { 
 
    // Take copy of nodes array, so that the original is not mutated 
 
    var nodes = nodes.map(node => ({ 
 
     id: node.id, 
 
     childrenSet: new Set(node.parentOf), // convert to Set for fast look-up 
 
     childrenSet2: new Set(node.parentOf), // copy 
 
     descendantSet: new Set(node.parentOf), // Will contain ALL descendants 
 
     sum: node.data 
 
    })); 
 
     
 
    // For faster lookup, create a Map with nodes keyed by their node.id. 
 
    var hash = new Map(nodes.map(node => [node.id, node])); 
 

 
    // Create complete descendants set for each node 
 
    nodesCopy = nodes.slice(); 
 
    while (true) { 
 
     // Get index of first node that has no (more) children 
 
     let i = nodesCopy.findIndex(node => !node.childrenSet.size); 
 
     if (i < 0) break; // Not found: then we're done 
 
     let id = nodesCopy.splice(i, 1)[0].id; // extract found node id 
 
     nodesCopy.forEach(parent => { 
 
      if (parent.childrenSet.has(id)) { // Found a parent of it 
 
       // Extend the parent's descendant list with the node's one 
 
       parent.descendantSet = new Set([...parent.descendantSet, 
 
               ...hash.get(id).descendantSet]); 
 
       // Don't consider this node any more. 
 
       // At one point the parent may become a leaf 
 
       parent.childrenSet.delete(id); 
 
      } 
 
     }); 
 
    } 
 
    if (nodesCopy.length) throw "Exception: graph has cycles"; 
 

 
    // Create true children sets (only direct children, without "redundancy"): 
 
    nodes.forEach(node => { 
 
     node.childrenSet = new Set(node.childrenSet2); 
 
     [...node.childrenSet] 
 
      // Collect descendants of children 
 
      .reduce((remote, id) => 
 
       new Set([...remote, ...hash.get(id).descendantSet]), new Set()) 
 
      // Remove any of those from the children's set 
 
      // (so no more "grand" children there) 
 
      .forEach(id => node.childrenSet.delete(id)); 
 
    }); 
 

 
    // Calculate the sums bottom-up 
 
    nodesCopy = nodes.slice(); 
 
    while (true) { 
 
     let i = nodesCopy.findIndex(node => !node.childrenSet.size); 
 
     if (i < 0) break; 
 
     let leaf = nodesCopy.splice(i, 1)[0]; 
 
     nodesCopy.forEach(parent => { 
 
      if (parent.childrenSet.has(leaf.id)) { 
 
       parent.sum += leaf.sum; 
 
       parent.childrenSet.delete(leaf.id); 
 
      } 
 
     }); 
 
    } 
 

 
    // Only return the information we need 
 
    return nodes.map(node => ({ id: node.id, sum: node.sum })); 
 
} 
 

 
// Sample data 
 
var nodes = [ 
 
    {id:1,data:29,parentOf:[]}, 
 
    {id:2,data:31,parentOf:[1,8,7]}, 
 
    {id:3,data:41,parentOf:[2,1]}, 
 
    {id:4,data:89,parentOf:[3,2,1]}, 
 
    {id:5,data:71,parentOf:[4,3,2,1,9,2,8,7]}, 
 
    {id:6,data:11,parentOf:[5,4,3,2,1]}, 
 
    {id:7,data:59,parentOf:[]}, 
 
    {id:8,data:43,parentOf:[7]}, 
 
    {id:9,data:97,parentOf:[2,8,7]} 
 
]; 
 

 
// Calculate sums 
 
var result = sumTree(nodes); 
 

 
// Output result 
 
console.log(result);

Answer 2

我想我失去了一些東西...... 請有何種後續一看：

1. 迭代所有節點
2. 總和node.data所有parents.data
3. 返回一個對象，只有id和sum屬性。

var nodes = [ 
 
    {id:1,data:29,parentOf:[]}, 
 
    {id:2,data:31,parentOf:[1,8,7]}, 
 
    {id:3,data:41,parentOf:[2,1]}, 
 
    {id:4,data:89,parentOf:[3,2,1]}, 
 
    {id:5,data:71,parentOf:[4,3,2,1,9,2,8,7]}, 
 
    {id:6,data:11,parentOf:[5,4,3,2,1]}, 
 
    {id:7,data:59,parentOf:[]}, 
 
    {id:8,data:43,parentOf:[7]}, 
 
    {id:9,data:97,parentOf:[2,8,7]} 
 
]; 
 

 

 
var result = nodes 
 
    .map((item, i, items) => { 
 
    let r = Object.create(null); 
 
    
 
    r.id = item.id; 
 
    
 
    r.sum = item.parentOf.reduce((prev, next, j) => { 
 
     let parent = (items.filter(x => x.id === next)[0] || {}); 
 
     let parentData = parent.data || 0; 
 
     
 
     return prev + parentData; 
 
    }, item.data); 
 

 
    return r; 
 
    }) 
 
; 
 

 
console.log('result', result);