# Algorithm for finding all the heaviest edges in a graph

We have a non directed, not necessarily connected graph $G=(V,E)$, that is represented by a adjacency list, and a weight function $w:E \to R$. All edges have distinct weight. An edge is "heavy" if there exists a simple cycle in $G$ that contains it, and it has the maximal weight in that cycle. The question is to give an algorithm which finds all of the heaviest edges in $G$.

My proposed algorithm:

1. Create an array $A$ of size $|V|$ where every cell represents a node $v_i$ in G. Mark all nodes as 'unexplored'.
2. Select the node $v_1$ in $G$ and run Prim's MST algorithm from it. Modify Prim's algorithm so that when a node is reached by the MST tree it is marked as 'explored' in $A$.
3. Scan the array $A$ linearly from the last node encountered as 'unexplored'. Each time a node marked 'unexplored' is found, do step 2 for it.
4. When $A$ is traversed completely, mark the group of all the edges in all the MSTs found as $E'$.
5. Return $E/E'$ — this is the group of heaviest edges.

The algorithm's correctness follows from the cycle property for MSTs, and that every edge has a distinct weight.

This algorithm is as efficient as running Prim's MST algorithm on a connected non directed graph — that is $O(E + V \lg V)$ with Fibonnaci heaps.

My questions is, is this is the optimal running time for this problem? I have a feeling this can somehow be done in linear time using DFS.

• Won't removing all the heavy edges give us the minimum spanning tree? So if there was a linear solution for this problem, we would also have a linear solution for the minimum spanning tree problem. Jul 30, 2016 at 12:23

You may find the $O(\left\vert{E}\right\vert\log{}\left\vert{V}\right\vert)$ complexity preferable to the $O(\left\vert{E}\right\vert+\left\vert{V}\right\vert\log{}\left\vert{V}\right\vert)$, and it seems that would just require a different choice of data structures or using either Kruskal's or Borůvka's.
For complexity with no $\log{}$ factors, it seems (for lack of a known general linear, deterministic, MST algorithm) you need either dense graphs, integer weights, or to use the expected linear time MST algorithm below.