Find all critical edges of MST

Question

I have this question from Robert Sedgewick's book on algorithms.

Critical ribs. An MST rib whose removal from the graph will cause the MST weight to increase is called the critical edge. Show how to find all critical edges in a time plot proportional to E log E. Note. This question assumes that the weights of the edges (otherwise all edges in the MST are critical). A.

Please suggest an algorithm that solves this problem.

One approach that I can think of does the work on time My approach is to run the kruskal algorithm.

But whenever we encounter an edge whose insertion into the MST creates a cycle, and if this cycle already contains an edge with the same edge weight, then the already inserted edge 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 complete the task in time E log E.

Answer 1

Yes, your algorithm is correct. We can prove that by comparing the execution of the Kruskal algorithm with a similar execution, where the cost of some edge of MST e varies indefinitely. Until the first performance considers e, both versions are identical. After e, the first execution has fewer components than the second. This condition remains until the edge e 'is considered, which in the second execution combines the components that will have e. Since the edge e is the only difference between the forests constructed so far, it must belong to the cycle created by e '. After e ', executions make the same decisions, and the difference in the forests is that the first execution has e, and the second has e'.

One way to implement this algorithm is to use a dynamic tree, a data structure that represents a labeled forest. One configuration of this ADT supports the following methods in logarithmic time .

• MakeVertex () - creates and returns a new vertex.
• Link (u, c, v) - vertices u and v should not be connected. Creates an unmarked edge from vertex u to vertex v with value c.
• Mark (u, v) - the vertices u and v should be the ends of the edge e. Signs e.
• Connected (u, v) - indicates whether the vertices u and v are connected.
• FindMax (u, v) - vertices u and v must be connected. Returns the endpoints of an unmarked edge along a unique path from u to v with a maximum cost along with this cost. The endpoints of this edge are indicated in the order in which they appear on the path.

I am not saying that in practice this is a good algorithm. Dynamic trees, such as Swiss army knives, are versatile, but complex and often not the best tool to work with. I urge you to think about how to take advantage of the fact that we can wait for all the ribs to be processed to find out what the critical ribs are.

Answer 2

I think the condition you are proposing is when the critical critical value is correct. But there is no need to actually find the cycle and check every edge of it.

The Kruskal algorithm adds edges in order of increasing weight, so the sequence of edge additives can be divided into blocks with equal weight additions to the edge. Inside each block with equal weight, if there is more than one edge connecting the same two components, then all these edges are non-critical, because you can choose any of the other edges instead. (I say that they are all non-critical, because in reality we are not providing a specific MST as part of the input - if we were then it would identify a specific edge to call non-critical. The edge that Kruskal actually chooses is just artifact of initial edge ordering or how sorting was done.)

But this is not enough: maybe after adding all the ribs of weight 4 or less in the MST, we find that there are 3 weights of 5 ribs connecting the pairs of components (1, 2), (2, 3) and (1, 3). Although none of the component pairs is connected to more than one of these three edges, we only need (any) of them 2 - using all 3 would create a loop.

For each block with equal weight, with the weight denoted by w, we really need to (conceptually) create a new graph in which each MST component so far (i.e. using edges having weight <w) is a vertex, and there is an edge between two vertices when there is an edge of weight-w between these components. (This can lead to multiple edges.) Then we run DFS on each component of this graph to find any cycles, and mark each edge that belongs to such a cycle as non-critical. DFS takes O (nEdges) time, so the sum of the DFS time for each block (the sum of the sizes of which is E) is O (E).

Note that the Kruskal algorithm takes O (Elog E) time, not O (E), as you seem to imply - although people like Bernard Chazel have come close to the linear construction of MST, TTBOMK is not there yet! :)