Jeff Schwab
11/20/2008 1:30:00 PM
BigBaz wrote:
> Given a graph G and a minimum spanning tree T, suppose that we
> decrease the weight of one of the edges that is not in T. Give an
> algorithm that finds the minimum spanning tree in the modified graph.
Enumerate all combinations of arcs in G into a sequence,
all_arc_combinations. Copy the combinations that are spanning trees
into a new sequence, all_spanning_trees. [1] Sort the spanning trees by
total weight, and return the least element of the sorted sequence.
Make sure you run your code to completion on a graph with at least a few
hundred nodes, so you'll know it's working.
[1] To tell whether a given combination of arcs is a spanning tree: A
priori (for efficiency), enumerate all combinations of nodes in G into a
set, all_node_combinations. Copy both nodes from each arc in the
arc-combination into a node-combination,
nodes_in_potential_spanning_tree. (Be careful to preserve duplicate
nodes, or else you might mis-identify a cyclic subgraph as a tree.) If
all_node_combinations contains nodes_in_potential_spanning_tree, the
arc-combinations is a spanning tree of G.