[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.c++

Question About Minimum Spanning Tree

BigBaz

11/20/2008 10:05:00 AM

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.

Thanks in advance.
7 Answers

Giff

11/20/2008 10:47:00 AM

0

BigBaz wrote:

> Thanks in advance.

What is the question? And what is the c++-related question?

Juha Nieminen

11/20/2008 1:08:00 PM

0

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.

You are supposed to do your homework yourself, not ask others to do it
for you.

Jeff Schwab

11/20/2008 1:30:00 PM

0

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.

red floyd

11/20/2008 2:53:00 PM

0

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.
>
> Thanks in advance.

A complete answer can be found here:

http://www.parashift.com/c++-faq-lite/how-to-post.ht...

Hope that helps.

BigBaz

11/20/2008 5:09:00 PM

0

On Nov 20, 9:53 am, red floyd <no.spam.h...@example.com> wrote:
Yes, I will try to do it myself. But this algorithm is different from
the normal algorithm of finding mst, otherwise the question will just
ask me how to find a mst. So clearly there's some difference. Any help
would be appreciated.

Jeff_Schwab, is your algorithm efficient? Thanks!



> 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.
>
> > Thanks in advance.
>
> A complete answer can be found here:
>
> http://www.parashift.com/c++-faq-lite/how-to-post.ht...
>
> Hope that helps.

Jeff Schwab

11/20/2008 5:35:00 PM

0

BigBaz wrote:
> Jeff_Schwab, is your algorithm efficient? Thanks!

No. The algorithm I posted is so remarkably inefficient that it is
completely impractical. That's sort of why I posted it; you haven't
made any apparent effort to even think about solutions to the problem.
This isn't really the right place to ask a pure CS question, anyway.

Good luck.

Erik Wikström

11/20/2008 6:09:00 PM

0

On 2008-11-20 11:04, 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.

T' = T

> Thanks in advance.

Your welcome.

--
Erik Wikström