TADM2E 6.9

Hints

Look very carefully at the definition of T, versus the definition of an MST.

Part A

The problem explicitly states that T is a "minimum weight connected subset", not "minimum weight connected subset with exactly N-1 edges", so it doesn't have to be an MST. If all weights are positive or zero, then T happens to be the same as the MST, but if negative weights are allowed, all negative weight edges must be included in T to drive the total as low as possible.

Part B

The easiest is just to run a preprocessing pass before running Kruskal's algorithm. Add all edges with negative weight, and all nodes connected to those edges. Then run Kruskal's algorithm normally until it is finished.

---

Part B alternative solution

DFS on a graph to determine whether it contains edges with a negative weight, maintaining pointer MIN_E to one edge with the lowest non-negative weight
I. If there are no edges with a negative weight, then return MIN_E
- If all edges have a non-negative weight, then the minimum weight subset is the subset of 1 edge with the lowest weight
- A subgraph of 1 edge is connected

II. If there are edges with a negative weight, then apply the Kruskal's algorithm
- Sort edges by their weight
- For each connectivity component, the total weight is stored in its representative, representative's weight updates in disjoint_set's union function, initial weight = 0
- Maintaining pointer MIN on the component with the lowest weight
- Loop over all edges
- - If edge's weight is negative, union components, if united component's weight is less than MIN, update MIN, continue
- - If edge's weight is positive and at least one of the components for union has a non-negative weight, continue
- - - Union with positive component via a positive edge can only increase weight, so the edge is skipped
- - If edge's weight is positive, weights of both components for union are negative, and (edges weight + weight of each component is negative), union components
- - - At this step, the algorithm does union 2 components with a negative weight via positive edge
- - - The weight of the combined component is less than the weight of each component separately, even though an edge with a positive weight was used
- - - If the weight of the combined component is less than MIN, update MIN
- return MIN

--Bkarpov96 (talk) 14:47, 22 July 2020 (UTC)