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.