TADM2E 6.9

From Algorithm Wiki
Revision as of 18:47, 23 April 2015 by Dentin (talk | contribs) (create page)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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.