CODEWITHSUNDEEP
algorithmgraph
Retr0spect
Retr0spect

Reputation: 187

Undirected Graph: Minimum Spanning Tree with few red edges as possible

I am not sure how to proceed with this problem.

Given an undirected graph, with each edge having color either red or blue. How can I find the minimum spanning tree which contains few red edges as possible, in time complexity (O(m + n) log n). Where m vertices and n are edges.

Any help will be greatly appreciated.

Upvotes: 1

Views: 805

Answers (2)

Pham Trung
Pham Trung

Reputation: 11294

As far as I can see, I think you have answered your own question. By assigning weight to the edges, red weights 1 and blue weights 0, the problem become the classical finding minimum spanning tree, which has time complexity O((m + n) log n).

Upvotes: 1

David
David

Reputation: 953

Start by finding all minimum spanning trees. Then count the edges of each tree and select the tree with fewest red. This is about modifying an algorithm for finding minimum spanning trees and you should be able to find examples.

If I misunderstood the question and the objective is to minimize red edges so that the spanning tree found may no longer be minimum: start by finding all possible spanning trees. Then select the tree with the fewest red edges.

Upvotes: 0

Related Questions