algorithm - 合并无向图中的循环以创建树

Question

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

例如下图的解:

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

会是

A--BCGI--DEH--F
           \
            J

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

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

Answer 1

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

这听起来很像您已经想到的:)。但是，如果您使用 union-find 数据结构来跟踪合并而不是实际修改图形，那就容易多了。参见 http://www.algorithmist.com/index.php/Union_Find