2
$\begingroup$

I've looked through CS SE and I've found a page that said you could find use BFS to find a MST if the edges are unweighted, but what if the edges are directed?

Given a directed graph between V vertices, I'm trying to find the minimum directed edges I need to add in order for every vertex to be connected to every other vertex.

Is MST the way to go? Or, is there another way I'm not thinking of.

I apologize if this question is too easy, as I am very new to programming. I appreciate any help. Thanks!

$\endgroup$
  • $\begingroup$ Should I change the question to something that relates more directly to my problem? $\endgroup$ – NL628 Jan 2 '18 at 2:41
  • 2
    $\begingroup$ So since we are talking about unweighted graph, any tree with all vertices in it will be the MST. However note that you may have a bad choice of starting node and your DFS may not give you all the nodes. So, you need to keep track of vertices not reached and do DFS from them too and connect it all. You will get a tree with multiple roots. Does that help? $\endgroup$ – User Not Found Jan 2 '18 at 5:17
2
$\begingroup$

This is known as an arborescence. There are algorithms for this problem, such as the Chu-Liu/Edmonds algorithm, but they are more complex than just doing a BFS. See also https://stackoverflow.com/q/21991823/781723.

$\endgroup$

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.