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

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