CODEWITHSUNDEEP
algorithmgraph-theorygraph-algorithmdepth-first-searchbreadth-first-search
Pranjal Verma
Pranjal Verma

Reputation: 147

How to traverse on only a cycle in a graph?

I'm attempting ch23 in CLRS on MSTs, here's a question:

Given a graph G and a minimum spanning tree T , suppose that we decrease the weight of one of the edges not in T . Give an algorithm for finding the minimum spanning tree in the modified graph.

A solution I found was to add this new changed edge in T, then exactly one simple cycle is created in T, traverse this cycle and delete the max-weight edge in this cycle, voila, the new updated MST is found!

My question is, how do I only traverse nodes on this simple-cycle? Since DFS/BFS traversals might go out of the cycle if I, say, start the traversal in T from one endpoint of this newly added edge in T.

One solution I could think of was to find the biconnected components in T after adding the new edge. Only one BCC will be found, which is this newly formed simple-cycle, then I can put in a special condition in my DFS code saying to only traverse edges/nodes in this BCC, and once a back-edge is found, stop the traversal.

Edit: graph G is connected and undirected btw

Upvotes: 1

Views: 295

Answers (1)

dWinder
dWinder

Reputation: 11642

Your solution is basically good. To make it more formal you can use Tarjan's bridge-finding algorithm

This algorithm find the cut-edges (aka bridges) in the graph in linear time. Consider E' to be the cut-edges set. It is easy to prove that every edge in E' can not be on circle. So, E / E' are must be the cycle in the graph.

You can use hash-map or array build function to find the difference between your E and the cut-edges set

From here you can run simple for-loop to find the max weight edge which you want to remove.

Hope that help!

Upvotes: 1

Related Questions