Velocity Reviews > C++ > Question About Minimum Spanning Tree

# Question About Minimum Spanning Tree

BigBaz
Guest
Posts: n/a

 11-20-2008
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.

Giff
Guest
Posts: n/a

 11-20-2008
BigBaz wrote:

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

Juha Nieminen
Guest
Posts: n/a

 11-20-2008
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.

BigBaz
Guest
Posts: n/a

 11-20-2008
On Nov 20, 9:53*am, red floyd <(E-Mail Removed)> 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.

>

>
> A complete answer can be found here:
>
> http://www.parashift.com/c++-faq-lit...t.html#faq-5.2
>
> Hope that helps.

Erik Wikström
Guest
Posts: n/a

 11-20-2008
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

--
Erik Wikström