圖形節點是否可以維護對其父項的引用列表？

我有一個DAG實現，可以完美地滿足我的需求。我將它用作我的一個項目的內部結構。最近，我遇到了一個用例，如果我修改節點的屬性，我需要將該屬性傳播給它的父母，並一直傳播到根。我的DAG中的每個節點當前都有一個鄰接表，它基本上只是對該節點的子節點的引用列表。但是，如果我需要將更改傳播到此節點的父節點（並且此節點可以有多個父節點），那麼我需要一個對父節點的引用列表。圖形節點是否可以維護對其父項的引用列表？

這是可以接受的嗎？或者有更好的方法來做到這一點？維護兩份名單（一份給父母，一份給孩子）是否有意義？我想將父母添加到相同的鄰接表中，但這會給我每個父母 - 子女關係的週期（即，父母 - >孩子和孩子 - >父母）。

來源

2013-06-18 Vivin Paliath

這可能是實現它的最佳方式，本質上是構建反向DAG來傳播更改。問題是，如果一個節點的父母（或其父母等）連接到其中一個節點的孩子會發生什麼？變化會繼續無限傳播嗎？ – ardent

@ ardentsonata-如果圖形是DAG，則不會發生這種情況，因爲沒有任何循環。 – templatetypedef

@ardentsonata我在這種情況下維護並行DAG。在一個案例中，我有一個針對兒童的DAG，最終以一些「葉子」節點結尾。這是通過子引用列表完成的。在另一種情況下，我有一個DAG，從孩子們身上朝向根部。在這種情況下不會有循環，因爲每個列表都是獨立遍歷的。 –

這是從來沒有必要父指針存儲在每個節點上，但這樣做可以使事情運行速度快了很多，因爲你確切地知道在哪裏看，以便找到父母。在你的情況下，這是完全合理的。

作爲一個類推 - 二叉搜索樹的許多實現將存儲父指針，以便他們可以更容易地支持旋轉（需要訪問父代）或刪除（可能需要知道父代節點）。同樣，一些更復雜的數據結構（如斐波那契堆）在每個節點中使用父指針，以更高效地實現減鍵操作。

用於存儲父母列表的內存開銷不會太差 - 您現在基本上對每條邊進行重複計算：每個父級存儲一個指向其子級的指針，並且每個子級都存儲一個指向其父級的指針。

希望這有助於！

來源

2013-06-18 22:43:22 templatetypedef

謝謝！這基本上是我正在尋找的。我只是想知道這種方法是否有意義和/或有先例。 –

圖形節點是否可以維護對其父項的引用列表？

回答

相關問題