1

Question:

if I assume that I ran Depth First Search on a digraph $G,$ and obtained a directed spanning forest $F.$ I am interested in the set $R$ of vertices reachable from a given fixed vertex $a \in V (G).$ How do I Show in general set $R$ of vertices cannot be obtained from directed spanning forest $F$?

Answer:

Can I answer it by saying that if I have a digraph of $G:= (\{1,2,3,4\},\{(1,2),(3,4)\}$ and i perform Depth First Search $(G, 1)$ which will result in $(\{1,2\}, \{(1,2)\})$ whereby vertex $1$ is unreachable. However, how is it even a directed spanning forest if I only obtain only vertex $1$ and $2$ which is not a directed spanning forest but rather a forest. IF not how should I answer it so that the result is a spanning forest?

TheCodeLearner
  • 35
  • 4
  • 1
    Can you please clarify "How do I Show in general set of vertices cannot be obtained from directed spanning forest ? " ? – A.G. Jan 01 '20 at 23:15
  • the question wants me to show the set R vertices which cannot be obtained from directed spanning forest F after performing DFS – TheCodeLearner Jan 01 '20 at 23:18
  • 1
    The definition of a spanning forest is that all nodes are spanned, i.e. reached. Unless restarted fron a non-reached node, DFS will produce a tree rather than a forest. – A.G. Jan 01 '20 at 23:31
  • @A.G. I think that in the question being asked, the graph may have multiple components, so DFS is called on each component separately. – Ekesh Kumar Jan 02 '20 at 00:13
  • @A.G. since there is multiple components, then how do I know which set of vertex is non-reachable – TheCodeLearner Jan 02 '20 at 12:44

1 Answers1

1

First you pick an initial node. As DFS progresses it will mark vertices as visited or seen. At the end, unseen vertices are those that cannot be reached by starting with the chosen initial node. The set of visited nodes corresponds to the first connected component (that to which the initial node belongs). If you want the full forest you then need to restart DFS from an unvisited node (and repeat).

A.G.
  • 2,781