java - 最小化图中的桥数

Question

我试图解决一个问题，基本上可以简化为:
给出一组从 1 到 N 编号的 N 个节点和 M 个边，其中 N<10000 和 M<100000 ,
找到一条边(u,v)，当添加到图中时——最小化图中的桥数。
如果有有许多这样的边 - 打印具有最低词典编纂值(value)的边。
解决此问题的有效方法是什么？

Answer 1

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

1) 找出图中所有的桥。

2) 现在假设桥是您想要在图形中唯一的边。您只保留网桥并在大节点中加入网桥之间的所有节点。

3) 你现在有一棵树。边是桥梁，节点是结合了先前图中节点的“大节点”。

4) 我们称这个森林图为 T。

5) 连接图 T 中的任意两个节点，创建一个循环。循环中的任何边都不是桥。

6) 第 5 点暗示解决方案是通过创建可能的最长循环找到的。您只需找到两个节点之间距离最长的节点即可做到这一点。

7) 您可以在图中找到距离最长的节点。这里是如何讨论的: A linear-time algorithm for finding the longest distance between two nodes in a free tree?

如果有任何一点需要进一步解释，请告诉我。