include an edge and produce spanning tree with least weight among those having edge

0
votes

I wish to find minimum spanning tree of graph G such that it includes and edge e and its weight is minimum of all those spanning trees which have edge e.If i include edge e and then run prime or kruskals will it work?

1
algorithmprims-algorithmkruskals-algorithm

1 Answers

2
votes

You can just set the edge weight of that edge (and any other edge you want to include in the spanning tree that would keep it a tree) by setting its weight to 0 and run your favorite MST algorithm.