algorithm - 通过 BFS 在无向图中查找关节顶点

Question

我对无向图有一个问题，听起来像这样：“对图进行广度优先遍历并列出图的关节点。”。我发现只有使用 DFS 来查找关节顶点的算法。有没有办法用 BFS 找到这些顶点？谢谢你。

更新：删除每个节点，然后在剩余的图上执行 BFS 怎么样？如果它覆盖所有节点，则删除的节点不是关节点。我知道它效率低下，但我认为没关系。

Answer 1

并非没有做一堆额外的工作。

原因是，如果不查看它的子节点、其子节点的子节点等，以找出哪些以某种方式连接回根顶点，则无法确定一个点是否为关节点。深度优先搜索会自动为您执行此操作。广度优先搜索没有。

您可以模拟它，但只能通过执行广度优先搜索然后记住所有中间状态以进行深度优先搜索。这是很多开销而没有真正的收益。