1
$\begingroup$

I have recently been doing some research into algorithms for finding minimum spanning trees in graphs, and I am interested in the following problem:

Let $G$ be an undirected graph $G=(V, E)$, $c(e)$ is black or white for each edge $e$ and weights $1\leq W(e)\leq 100$ for each $e$.

I want to find if we have a minimum spanning tree with only white edge in graph $G$.

My solution is to give each white edge $0$ weight and run Prim's algorithm. We will add to a new parameter $w=0$ the weight of each edge that we adding to the minimum spanning tree. After the end of running prim's algorithm, we will check if ($w>0$) return false, else return true.

Is it can work? Is there something more efficient?

Thanks

$\endgroup$
2
$\begingroup$

Just remove all of the black edges from the graph and run a normal Prim algorithm, the black edges are useless. (in other words, disregard black edges, treat black edges the same way you treat non-existent edges).

$\endgroup$
  • $\begingroup$ PS:I use kruskal most times, instead of Prim. $\endgroup$ – Jorge Fernández Hidalgo Jan 21 '17 at 16:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.