algorithm - DFS 计算关节点的孤立节点

Question

我有一个图表和一个起始节点。对于所有节点，我想使用 DFS 找出当我删除图中的每个节点时有多少节点被隔离。

例如，如果我从固定节点 1 开始，然后移除节点 2，我将拥有多少个孤立节点？如果我删除节点 3？

我知道我可以只对所有节点执行 DFS(每次删除一个不同的节点)，但这样做我将不得不为每个节点导航一次图形，我想只运行一次就解决它。

有人告诉我它有 O(|V|*||A|)，|V|= 边数，|A|= 节点数。

我一直在玩 prenums 和 postnums，但没有成功。

Answer 1

令 N 为顶点数，M 为边数。如果您只是想要一个 O(NM) 解决方案，就像您所说的那样，您不需要为每个顶点运行 DFS。

每个 DFS 的复杂度为 O(N+M)，因此总复杂度为 O(N(N+M)) = O(N²+NM)。通常我们的边比顶点多，所以 NM 的增长速度比 N² 快得多，我们可以说复杂度为 O(NM)。但是请记住，如果您在每一步都物理删除当前顶点，您的实现将具有更糟糕的复杂性，因为物理删除一个顶点意味着从许多邻接列表中删除条目，无论您如何表示，这都是昂贵的图形。有一个实现技巧可以加快这个过程:不是在每个 DFS 之前物理删除当前顶点，而是将顶点标记为已删除，并且当您在 DFS 期间浏览邻接列表时，只需忽略标记的顶点。

但是，我觉得您可以使用 Tarjan 的寻找关节点的算法在 O(N+M) 中解决这个问题。该算法将找到每个顶点，当从图中删除时，将图形分成多个连接的组件(这些顶点称为关节点)。很容易看出，如果删除一个不是关节点的顶点，就不会有孤立的顶点。但是，如果您删除一个关节点，您会将图分成两部分 G 和 G'，其中 G 是起始顶点的连通分量，而 G' 是图的其余部分。 G' 中的所有顶点都是孤立的，因为如果从起始顶点运行 DFS，则无法到达它们。我认为你可以有效地找到每个顶点删除的 G' 的大小，也许你甚至可以在运行 Tarjan 的时候这样做。如果我找到解决方案，我可以稍后编辑此答案。

编辑:我设法用 O(N+M) 解决了这个问题。我会给出一些提示，以便您自己找到答案:

1. 每个无向图都可以分解为(不是不相交的)双连通分量集:每个双连通分量都是图中顶点的一个子集，即使您删除了图的任何顶点，该子集中的每个顶点都将保持连接图

2. 如果去掉任何一个不是关节点的顶点，这个顶点的答案显然是N-1

3. 如果你删除一个关节点，起始顶点的同一个双连通分量中的每个顶点仍然是可访问的，但你不知道其他双连通分量。别担心，有一种方法可以高效地找到它

4. 您可以压缩图 B 的双连通分量中的每个图 G。压缩算法很简单:每个双连通分量都成为 B 中的一个顶点，并且您链接共享某个关节点的双连通分量。我们可以证明生成的图 B 是一棵树。您必须以某种方式使用这棵树才能解决步骤 4 中出现的问题

祝你好运!