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!

Improve this question
$\endgroup$
2
  • $\begingroup$ Should I change the question to something that relates more directly to my problem? $\endgroup$
    – NL628
    Jan 2, 2018 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, 2018 at 5:17

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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