Difference between revisions of "TADM2E 6.6"
From Algorithm Wiki
(Fucs moved page TADM2E 6.6 to Penis) |
|||
| (One intermediate revision by one other user not shown) | |||
| Line 1: | Line 1: | ||
| − | # | + | <pre> |
| + | Special cases when adding an edge e = (u, v) | ||
| + | 1) u or v not in the T's set of vertices, i.e. a vertex and an edge were added to G, include e' in T, return | ||
| + | 2) T has an edge e' = (u, v) whose weight <= the weight of e, then e should not be included in T, return | ||
| + | 3) T has an edge e' = (u, v) whose weight is > the weight of e, then replace e' with e, return | ||
| + | |||
| + | Include e in T, now T contains n vertices and n edges. | ||
| + | - Minimal spanning tree is connected => vertex U was reachable from V and V was reachable from U before adding e => now T contains a loop | ||
| + | Detect a loop using DFS(T) # O(n + n) = O(2*n) = O(n) | ||
| + | Remove the edge with the highest weight from the loop so that the graph T becomes a minimal spanning tree again # O(n) | ||
| + | </pre> | ||
| + | --[[User:Bkarpov96|Bkarpov96]] ([[User talk:Bkarpov96|talk]]) 12:17, 22 July 2020 (UTC) | ||
Latest revision as of 08:15, 23 July 2020
Special cases when adding an edge e = (u, v) 1) u or v not in the T's set of vertices, i.e. a vertex and an edge were added to G, include e' in T, return 2) T has an edge e' = (u, v) whose weight <= the weight of e, then e should not be included in T, return 3) T has an edge e' = (u, v) whose weight is > the weight of e, then replace e' with e, return Include e in T, now T contains n vertices and n edges. - Minimal spanning tree is connected => vertex U was reachable from V and V was reachable from U before adding e => now T contains a loop Detect a loop using DFS(T) # O(n + n) = O(2*n) = O(n) Remove the edge with the highest weight from the loop so that the graph T becomes a minimal spanning tree again # O(n)
