6

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

这是一个例子：

在此处输入图像描述

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

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

关于如何做到这一点的任何帮助或建议都会很棒。

谢谢！

4

2 回答 2

6

我假设以下情况属实：

  • 该图是非循环的。您在评论中提到了这一点，但我想明确表示这是一个开始的假设。
  • 有一组已知的根节点。我们需要有某种方式知道哪些节点总是被认为是可达的，我假设（不知何故）这些信息是已知的。
  • 初始图不包含任何多余的节点。也就是说，如果初始图包含任何应该删除的节点，那么它们已经被删除了。这允许算法通过保持每个节点都应该存在的不变量来工作。

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

  1. 该节点在根可达节点集中，或
  2. 该节点有一个父节点，该父节点位于可到达的根节点集中。

因此，每当您从图中删除一个节点时，可能需要删除的唯一节点就是该节点的后代。如果您删除的节点在根集中，您可能需要修剪很多图，如果您删除的节点是其自己的后代很少的后代节点，那么您可能需要做的很少。

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

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

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

  • 创建工作清单 W。
  • 将要删除的节点 v 添加到 W。
  • 虽然 W 不为空：
    • 从 W 中删除第一个条目；叫它w。
    • 对于 w 的每个孩子：
      • 如果该孩子只有一个父母，请将其添加到 W。
    • 从图中删除 w。

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

希望这可以帮助！

于 2012-01-08T20:50:03.793 回答
5

让我为您提供解决您的任务的 python networkX 代码：

import networkx as nx
import matplotlib.pyplot as plt#for the purpose of drawing the graphs
DG=nx.DiGraph()
DG.add_edges_from([(3,8),(3,10),(5,11),(7,11),(7,8),(11,2),(11,9),(11,10),(8,9)])
DG.remove_node(11)

connected_components 方法令人惊讶地不适用于有向图，因此我们将图变为无向图，找出未连接的节点，然后将它们从有向图中删除

UG=DG.to_undirected()
not_connected_nodes=[]
for component in nx.connected_components(UG):
    if len(component)==1:#if it's not connected, there's only one node inside
        not_connected_nodes.append(component[0])
for node in not_connected_nodes:
    DG.remove_node(node)#delete non-connected nodes

如果要查看结果，请在脚本中添加以下两行：

nx.draw(DG)
plt.show()
于 2012-01-09T15:35:36.257 回答