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$

1 Answer 1

Reset to default
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$
1
  • $\begingroup$ PS:I use kruskal most times, instead of Prim. $\endgroup$ Commented Jan 21, 2017 at 16:28

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.