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?



1 Answer 1


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).

  • $\begingroup$ PS:I use kruskal most times, instead of Prim. $\endgroup$
    – Asinomás
    Jan 21, 2017 at 16:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .