我有一个非常适合我的需求的 DAG 实现。我将它用作我的一个项目的内部结构。最近，我遇到了一个用例，如果我修改了一个节点的属性，我需要将该属性传播到它的父节点，一直传播到根节点。我的 DAG 中的每个节点当前都有一个邻接列表，它基本上只是对节点子节点的引用列表。但是，如果我需要将更改传播到该节点的父节点(并且该节点可以有多个父节点)，我将需要一个父节点引用列表。
这可以接受吗？或者有更好的方法吗？保留两份 list (一份给 parent ，一份给 child )是否有意义？我想将 parent 添加到同一个邻接列表中，但这会给我每个父子关系的循环(即父->子和子->父)。
最佳答案
永远没有必要在每个节点中存储父节点指针，但这样做可以使事情运行得更快，因为您确切地知道在哪里寻找父节点。在您的情况下，这是完全合理的。
打个比方——许多二叉搜索树的实现将存储父节点指针，以便它们可以更轻松地支持旋转(需要访问父节点)或删除(可能需要知道父节点)。类似地，一些更复杂的数据结构(如斐波那契堆)在每个节点中使用父指针，以便更有效地实现减少键操作。
存储父节点列表的内存开销不会太糟糕 - 您现在实际上是在重复计算每条边:每个父节点存储一个指向其子节点的指针，每个子节点存储一个指向其父节点的指针。
希望这对您有所帮助!
关于algorithm - 图节点可以维护对其父节点的引用列表吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/17179938/