Find all critical edges of an MST
algorithm, graph-algorithm, graph-theory, minimum-spanning-tree
Solution
Yes, your algorithm is correct. We can prove that by comparing the execution of Kruskal's algorithm to a similar execution where the cost of some MST edge e is changed to infinity. Until the first execution considers e, both executions are identical. After e, the first execution has one fewer connected component than the second. This condition persists until an edge e' is considered that, in the second execution, joins the components that e would have. Since edge e is the only difference between the forests constructed so far, it must belong to the cycle created by e'. After e', the executions make identical decisions, and the difference in the forests is that the first execution has e, and the second, e'.
One way to implement this algorithm is using a dynamic tree, a data structure that represents a labelled forest. One configuration of this ADT supports the following methods in logarithmic time.
- MakeVertex() - constructs and returns a fresh vertex.
- Link(u, c, v) - vertices u and v must not be connected. Creates an unmarked edge from vertex u to vertex v with cost c.
- Mark(u, v) - vertices u and v must be endpoints of an edge e. Marks e.
- Connected(u, v) - indicates whether vertices u and v are connected.
- FindMax(u, v) - vertices u and v must be connected. Returns the endpoints of an unmarked edge on the unique path from u to v with maximum cost, together with that cost. The endpoints of this edge are given in the order that they appear on the path.
I make no claim that this is a good algorithm in practice. Dynamic trees, like Swiss Army knives, are versatile but complicated and often not the best tool for the job. I encourage you to think about how to take advantage of the fact that we can wait until all of the edges are processed to figure out what the critical edges are.
Problem
I have this question from Robert Sedgewick's book on algorithms. Critical edges. An MST edge whose deletion from the graph would cause the MST weight to increase is called a critical edge. Show how to find all critical edges in a graph in time proportional to E log E. Note: This question assumes that edge weights are not necessarily distinct (otherwise all edges in the MST are critical). Please suggest an algorithm that solves this problem. One approach I can think of does the job in time E.V. My approach is to run the kruskal's algorithm. But whenever we encounter an edge whose insertion in the MST creates a cycle and if that cycle already contains an edge with the same edge weight, then, the edge already inserted will not be a critical edge (otherwise all other MST edges are critical edges). Is this algorithm correct? How can I extend this algorithm to do the job in time E log E.