Search code examples
algorithmrecursiongraphmaxcycle

Finding the heaviest edge in the graph that forms a cycle

Given an undirected graph, I want an algorithm (inO(|V|+|E|)) that will find me the heaviest edge in the graph that forms a cycle. For example, if my graph is as below, and I'll run DFS(A), then the heaviest edge in the graph will be BC. (*) In this problem, I have at most 1 cycle.

enter image description here

I'm trying to write a modified DFS, that will return the desired heavy edge, but I'm having some trouble.

Because I have at most 1 cycle, I can save the edges in the cycle in an array, and find the maximum edge easily at the end of the run, but I think this answer seems a bit messy, and I'm sure there's a better recursive answer.

Solution

  • I think the easiest way to solve this is to use a union-find data structure (https://en.wikipedia.org/wiki/Disjoint-set_data_structure) in a manner similar to Kruskal's MST algorithm:

    1. Put each vertex in its own set
    2. Iterate through the edges in order of weight. For each edge, merge the sets of the adjacent vertices if they're not already in the same set.
    3. Remember the last edge for which you found that its adjacent vertices were already in the same set. That's the one you're looking for.

    This works because the last and heaviest edge that you visit in any cycle must already have its adjacent vertices connected by edges you visited earlier.