# BFS on directed graph with disjointed edges?

There is a graph (directed and unweighted) and a collection of nodes. If I want to find a tree that has all those nodes in it and potentially some other ones as well, would BFS be a good algorithm to use for this case? Can BFS find, let's say as an example, two nodes that are not directly connected but after going to an intermediate node then they are kind of connected?

• Please ask only one question per post. If you have two questions, you can ask them separately in two different posts. I have edited out your second question. You can find it in the revision history and ask it separately if you wish.
– D.W.
Commented Jun 7 at 6:28
• What is a tree in this setting? Which requirements do you have for the directedness? Commented Jun 7 at 6:55

Given a graph $$G=(V,E)$$ and a set of nodes $$N \subseteq V$$, find a tree $$T$$ that spans over all nodes in $$N$$. Here, $$T$$ is a spanning tree of the induced subgraph of a subset $$S$$ of vertices where $$N \subseteq S \subseteq V$$.
Since you have no optimization criterion here, finding a spanning tree of $$G$$ itself should suffice. If there exists a rooted directed spanning tree in $$G$$, you can, of course, find that using BFS or DFS by possibly starting it from every vertex. Also see this post for your reference.
• The induced subgraph of $N$ may not be connected. You might have to add additional vertices to make it a single connected component, which can give you the required tree $T$. Commented Jun 7 at 17:11
• I am curious to know from where your problem has originated or been motivated. If was inspired by some real life problem, shouldn't there be some objective function to optimize? To make the problem more interesting and, thus, harder, one might consider some optimization criterion on the size of $S$. Commented Jun 7 at 17:13