分區壓縮及如何壓縮節點根

enter image description here 分區壓縮及如何壓縮節點根

我試圖壓縮給定節點的所有祖先通過使它們指向參數節點傳遞到

private E compressToRoot (E e) throws IllegalArgumentException;

根

例如，在上面的圖片中，如果我執行了compressToRoot（D），那麼D將直接指向A，C將直接指向A.如果參數和根之間存在其他節點，則它們都指向A.

所有的實驗室els和箭頭存儲在兩個單獨的地圖中：我可以通過以下方法來完成此方法：（1）將D和根中的所有節點保存在一組中。（2）使設定點的所有元素（作爲父母）爲根（3）返回根。

但是，我被困在如何遍歷這個地圖到根。因此，對於該方法，我會做沿着

private E compressToRoot (E e) throws IllegalArgumentException { 
    Set<E> collectLables = new HashSet<E>(); 
E root = null; 

//get root. 
for (E cycle : parentMap.keys()) { 
    while (parentMap.get(e) != e) 
     e = parentMap.get(e); 
     if (parentMap.get(e) == e) 
      root = cycle; 
} 


//collect all labels from parameter to root. 
for (E element : parentMap.keys()) { 
    while (parentMap.get(e) != root) { 
     collectLables.add(element); 
    } 
} 


}

線的東西，但我不知道我怎麼可以通過給定節點一路到根的父母週期。

來源

2012-12-01 user1766888

爲什麼E指向圖像中的A？ – Origin

遞歸是很漂亮，但有利於迭代方法，如果最長路徑到根的長度可能會很大。你不想用完堆棧。

private E compressToRoot(E node) { 
    if (parentMap.get(node) != node) 
     parentMap.set(node, compressToRoot(node)); 
    return parentMap.get(node); 
} 

private E compressToRoot(E cursor) { 
    E node; 
    ArrayList<E> nodes = new ArrayList<E>(); 
    while ((node = parentMap.get(cursor)) != cursor) { 
     nodes.add(cursor); 
     cursor = node; 
    } 

    for (node : nodes) 
     parentMap.set(node, cursor); 

    return cursor; 
}

來源

2012-12-01 05:18:23 goat

我被困在如何遍歷這個地圖到根。

看來你對「根」的定義是唯一指向自己的節點。這不是特別有效，但你可以隨便找一個這樣的元素：

E findRoot(Map<E, E> parentMap) { 
    for (Map.Entry<E, E> entry: parentMap.entrySet() { 
     if (entry.key().equals(entry.value()) { 
      return entry; 
     } 
    } 

    // parentMap is empty, or the graph is corrupted 
    // handle this edge case however you want 
    return null; 
}

來源

2012-12-01 01:17:29

如果我不理解，請隨時澄清設計。 –

返回類型是Map.Entry 。那麼，如何確保只有參數節點的父節點指向此條目？（而不是像上面圖片中的其他一些節點，例如B？ – user1766888

我不知道，你看起來更像是一個通用圖表表示而不是樹，具體來說，它並不會立即對我產生很大的影響。如果你要存儲這樣的樹，那麼你需要編寫代碼來確保不變量是真實的。是否有一個特定的原因使用地圖來表示邊，而不是更典型的'Node'存儲對其子的引用（可選地帶有父引用）？ –

取決於Map的效率，略微有可能改進到rambo coder's answer above。你可以在不使用額外內存和ArrayList的開銷的情況下通過遍歷路徑兩次：

private E compressToRoot(E cursor) { 
    E cursor2 = cursor; 
    E node = parentMap.get(cursor); 
    while (node != cursor) { 
     cursor = node; 
     node = parentMap.get(node); 
    } 
    // Now cursor (and node) are the root.  

    node = parentMap.get(cursor2); 
    while (node != cursor2) { 
     parentMap.set(cursor2, cursor); 
     cursor2 = node; 
     node = parentMap.get(node); 
    } 

    return cursor; 
}

來源

2012-12-02 20:53:38

分區壓縮及如何壓縮節點根

回答

相關問題