DFS 计算关节点的孤立节点
DFS count isolated nodes for articulation points
我有一个图表和一个起始节点。我想知道当我删除图中的每个节点时，有多少节点被隔离，对于所有节点，使用 DFS。
例如，如果我从固定节点 1 开始，然后移除节点 2，我将有多少个孤立节点？如果我删除节点 3?
我知道我可以对所有节点进行 DFS（每次删除一个不同的节点），但这样做我将不得不为每个节点导航一次图形，我想只用一个来解决它 运行.
有人告诉我它有 O(|V|*||A|)，|V|= 边数，|A|= 节点数。
我一直在玩 prenums 和 postnums，但没有成功。
设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' 的大小，也许你甚至可以在 运行ning Tarjan 的时候这样做。如果我找到解决方案，我可以稍后编辑此答案。
编辑：我设法用 O(N+M) 解决了这个问题。我会给出一些提示，以便您自己找到答案：
每个无向图都可以分解为（不是不相交的）双连通分量集：每个双连通分量都是图中顶点的一个子集，即使您删除图的任何顶点
可以更改 Tarjan 的 O(N+M) 算法来查找桥接点和关节点，以查找双连通分量，查找哪些顶点属于每个双连通分量，或者哪些双连通分量包含每个顶点
如果你去掉任何一个不是关节点的顶点，这个顶点的答案显然是N-1
如果你删除一个关节点，起始顶点的同一个双连通分量中的每个顶点仍然是可访问的，但你不知道其他双连通分量。别担心，有一种方法可以高效地找到它
您可以压缩其双连通分量的图 B 中的每个图 G。压缩算法很简单：每个双连通分量都成为 B 中的一个顶点，并且 link 双连通分量共享一些关节点。我们可以证明生成的图 B 是一棵树。您必须以某种方式使用这棵树才能解决步骤 4
祝你好运！
我有一个图表和一个起始节点。我想知道当我删除图中的每个节点时，有多少节点被隔离，对于所有节点，使用 DFS。
例如，如果我从固定节点 1 开始，然后移除节点 2，我将有多少个孤立节点？如果我删除节点 3?
我知道我可以对所有节点进行 DFS（每次删除一个不同的节点），但这样做我将不得不为每个节点导航一次图形，我想只用一个来解决它 运行.
有人告诉我它有 O(|V|*||A|)，|V|= 边数，|A|= 节点数。
我一直在玩 prenums 和 postnums，但没有成功。
设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' 的大小，也许你甚至可以在 运行ning Tarjan 的时候这样做。如果我找到解决方案，我可以稍后编辑此答案。
编辑：我设法用 O(N+M) 解决了这个问题。我会给出一些提示，以便您自己找到答案：
每个无向图都可以分解为（不是不相交的）双连通分量集：每个双连通分量都是图中顶点的一个子集，即使您删除图的任何顶点
可以更改 Tarjan 的 O(N+M) 算法来查找桥接点和关节点，以查找双连通分量，查找哪些顶点属于每个双连通分量，或者哪些双连通分量包含每个顶点
如果你去掉任何一个不是关节点的顶点，这个顶点的答案显然是N-1
如果你删除一个关节点，起始顶点的同一个双连通分量中的每个顶点仍然是可访问的，但你不知道其他双连通分量。别担心，有一种方法可以高效地找到它
您可以压缩其双连通分量的图 B 中的每个图 G。压缩算法很简单：每个双连通分量都成为 B 中的一个顶点，并且 link 双连通分量共享一些关节点。我们可以证明生成的图 B 是一棵树。您必须以某种方式使用这棵树才能解决步骤 4
中出现的问题
祝你好运！