1
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – D.W.
    Commented Jun 7 at 6:28
  • 1
    $\begingroup$ What is a tree in this setting? Which requirements do you have for the directedness? $\endgroup$ Commented Jun 7 at 6:55

1 Answer 1

1
$\begingroup$

Assuming you want the following:

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.

$\endgroup$
6
  • $\begingroup$ So should I be extract the subgraph using the set of nodes (N) from graph G followed by doing the BFS on the subgraph? $\endgroup$
    – Caroline
    Commented Jun 7 at 16:34
  • $\begingroup$ 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$. $\endgroup$
    – codeR
    Commented Jun 7 at 17:11
  • $\begingroup$ 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$. $\endgroup$
    – codeR
    Commented Jun 7 at 17:13
  • $\begingroup$ Real life problem that the instructor decided to make it as challenging assignment/exam project. $\endgroup$
    – Caroline
    Commented Jun 7 at 17:45
  • $\begingroup$ How would one go about finding additional vertices to make it a single connected component? Is it doing BFS or DFS on each set of nodes (N)? I wanted to use Edmonds algorithm but given the shear size of the G, Im not sure if there is a package that can handle large graph file size. $\endgroup$
    – Caroline
    Commented Jun 7 at 17:47

Your Answer

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

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