给定一个无向图,我需要一个算法(inO(|V|+|E|)
)来找到图中形成循环的最重边。例如,如果我的图如下所示,我将运行DFS(A)
,那么图中最重的边将是BC
。
(*)在这个问题上,我最多有一个循环。
我试图写一个修改的dfs,这将返回所需的重边缘,但我有一些麻烦。
因为我最多有1个循环,我可以在数组中保存循环中的边,并且在运行结束时很容易找到最大的边沿,但是我认为这个答案看起来有点混乱,我确信有一个更好的递归答案。
最佳答案
我认为解决这个问题的最简单方法是使用union-find数据结构(https://en.wikipedia.org/wiki/Disjoint-set_data_structure),其方式类似于Kruskal的MST算法:
将每个顶点放在自己的集合中
按权重顺序遍历边对于每个边,合并相邻顶点的集合(如果它们不在同一集合中)。
记住最后一条发现其相邻顶点已在同一集中的边。你要找的就是那个。
这是因为您在任何循环中访问的最后一条最重的边必须已由您先前访问的边连接其相邻顶点。
关于algorithm - 在形成循环的图中找到最重的边,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/47960655/