Difference between revisions of "TADM2E 6.10"
From Algorithm Wiki
(Blanked the page) |
(Undo revision 877 | Why are u doing this? What's the point? It's wiki for learning book) |
||
| Line 1: | Line 1: | ||
| − | + | <pre> | |
| + | 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. | ||
| + | </pre> | ||
| + | --[[User:Bkarpov96|Bkarpov96]] ([[User talk:Bkarpov96|talk]]) 15:38, 22 July 2020 (UTC) | ||
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.
