algorithm - 下达从图中删除顶点的命令，这样它就不会断开图的连接

Question

这是 Steven Skiena 的算法设计中的一个问题（用于面试准备）：

图 G 的一个关节顶点是一个其删除断开 G 的顶点。设 G 是一个具有 n 个顶点和 m 个边的图。给出一个简单的 O(n + m) 找到 n 个顶点的删除顺序，这样没有删除会断开图的连接。

这就是我的想法：

1. 在图上运行 DFS 并不断更新每个节点最旧的可达祖先（根据它我们决定它是桥切节点、父可爱节点还是根切节点）

2. 如果我们找到叶节点（顶点）或不是关节顶点的节点，则将其删除。

3. 在 DFS 结束时，我们将在图中留下所有那些被发现是关节顶点的节点

由于关节顶点完好无损，该图将保持连接状态。我已经在几个图表上进行了尝试，它似乎有效，但对于这本书来说感觉太简单了。

Answer 1

假设图是连通的，那么任何随机节点都会到达一个子图，其生成树可以在不破坏图的连通性的情况下按后序删除。以这种方式重复，直到图形全部消失。

Answer 2

1. 利用DFS跟踪每个顶点的退出时间；
2. 按照记录的退出时间顺序删除顶点；

Answer 3

分两步：

1. 使用任何遍历算法制作图 DAG
2. 做拓扑排序

每一步都在不超过 O(m+n) 的情况下完成

Answer 4

如果我们总是一棵一棵地删除一棵树的叶子，树的其余部分仍然保持连接。这样做的一种特殊方法是在使用 DFS 或 BFS 遍历图时为每个顶点分配一个预订编号。按降序对顶点进行排序（基于预购编号）。从图中按该顺序删除顶点。请注意，叶子总是首先被删除。