在无向图中合并循环以创建树

Question

问题：给定一个带有周期的无向图，合并最少数量的节点以消除周期。

例如，下图的解决方案：

     G      H
    /     / 
A--B---C--D---E--F
     /        
     I          J

将

A--BCGI--DEH--F
           
            J

我对如何通过进行广度优先搜索并在检测到循环时将节点合并到根来解决此问题有一个粗略的想法，但这似乎有点复杂。我想知道这个问题是否有一个众所周知的算法。

顺便说一句：这不是家庭作业。 :)

Answer 1

1. 使用 BFS 或 DFS 创建生成树
2. 对于不在树中的每个边，将边的两个节点和路径上的所有节点合并到它们最近的公共祖先。

这听起来很像你已经想到:)。 但是，如果您使用联合查找数据结构来跟踪合并，而不是在进行时实际修改图形，则要容易得多。 见 http://www.algorithmist.com/index.php/Union_Find