在图中最小化桥的数量

Question

在图中最小化桥的数量

4

我正在尝试解决一个问题，基本上可以简化为以下内容：
给定一个由N个编号为1到N的节点和M条边组成的图，其中N<10000且M<100000，找到一条边(u,v)，将其添加到该图中，使得该图中的桥数量最小。如果有多个这样的边，则输出具有按字典序排序后最小值的那一条。
如何以高效的方式解决这个问题？

- Animesh Fatehpuria

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Neithrik · Accepted Answer

我认为这个问题非常难。以下是我能想到的解决方案概述：

1）找出图中的所有桥。

2）现在假设桥是您希望保留在图中的唯一边缘。您仅保留桥梁，并将所有桥之间的节点连接在一起。

3）现在您有了一棵树。边缘是桥，节点是“大节点”，它们组合了前一个图中的节点。

4）让我们称此森林图为T。

5）在图T中连接任意两个节点都会创建一个循环。循环中的任何边缘都不是桥梁。

6）第5点意味着通过创建最长可能的循环来找到解决方案。您可以通过查找距离最远的两个节点来简单地完成这项工作。

7）您可以在图中找到具有最长距离的节点。如何完成请参见此处：在自由树中查找两个节点之间的最长距离的线性时间算法？请让我知道是否需要进一步解释。