algorithm - 如何使用 networkx 删除有向图中的所有相关节点？

Question

我不确定我的问题的正确术语是什么，所以我只解释我想做什么。我有一个有向图，在我删除一个节点后，我希望所有独立相关的节点也被删除。

这是一个例子:

说，我删除了节点“11”，我希望节点“2”也被删除(在我自己的示例中，它们将是 2 以下的节点，现在也必须删除)因为它不是连接到主图了。请注意，不应删除节点“9”或“10”，因为节点“8”和“3”仍连接到它们。

我正在使用 python 库 networkx。我搜索了文档，但我不确定术语，所以我不确定这叫什么。如果可能的话，我想使用库提供的函数，而不是通过图形创建我自己的递归(因为我的图形非常大)。

任何有关如何执行此操作的帮助或建议都将非常有用。

谢谢!

Answer 1

我假设以下内容为真:

• 图是无环的。您在评论中提到了这一点，但我想明确表示这是一个初始假设。
• 有一组已知的根节点。我们需要某种方式来了解哪些节点始终被认为是可达的，并且我假设(以某种方式)此信息是已知的。
• 初始图不包含任何多余的节点。也就是说，如果初始图包含任何应删除的节点，则它们已被删除。这允许算法通过保持每个节点都应该存在的不变性来工作。

如果是这种情况，那么给定初始设置，节点在图中的唯一原因可能是

1. 该节点在根可达节点集中，或者
2. 该节点的父节点位于根可达节点集中。

因此，无论何时从图中删除一个节点，可能需要删除的唯一节点是该节点的后代。如果您删除的节点在根集中，您可能需要修剪很多图形，如果您删除的节点是一个后代节点，其后代很少，那么您可能需要做的事情很少。

鉴于此设置，删除一个节点后，您将需要扫描该节点的所有子节点，以查看其中是否没有其他父节点可以将它们保留在图中。由于我们假设图中唯一的节点是需要存在的节点，如果已删除节点的子节点至少有一个其他父节点，那么它应该仍在图中。否则，需要删除该节点。因此，执行删除步骤的一种方法是以下递归算法:

• 对于要删除的节点的每个子节点:
  • 如果该节点只有一个父节点:(它必须是我们要删除的节点)
    • 递归地从图中删除该节点。
• 从图中删除指定的节点。

不过，这可能不是直接实现的好算法，因为如果您有一个大图，所涉及的递归可能会非常深。因此，您可能希望使用像这样的工作列表算法来实现它:

• 创建工作列表 W。
• 将要删除的节点 v 添加到 W。
• 当 W 不为空时:
  • 从 W 中删除第一个条目；称它为w。
  • 对于 w 的每个 child :
    • 如果那个 child 只有一个 parent ，将其添加到 W。
  • 从图中删除 w。

这最终是最坏情况下的 O(m) 时间，其中 m 是图中边的数量，因为理论上每条边都必须扫描。但是，假设您的图形中有一些冗余，它可能会快得多。

希望这对您有所帮助!