Difference between revisions of "TADM2E 6.10"
From Algorithm Wiki
(6.10 solution) |
(Undo revision 877 | Why are u doing this? What's the point? It's wiki for learning book) |
| (One intermediate revision by one other user not shown) | |
(No difference)
| |
Latest revision as of 08:12, 23 July 2020
1. DFS from any vertex when found back edge add it to F. 2. Applying the Kruskal's algorithm - First multiply the weights of all edges by -1 - If an edge is found during the algorithm execution, both ends of which belong to the same component, add it to F By multiplying all edges by -1, the edges with the highest weight will be processed first => the edges with the lowest weight will be added to F An alternative statement of the problem from point 2 is to find the complement to the maximum spanning tree.
