Register

GO Classes DPP | GATE CS, DA | Algorithms | DFS Tree in DAG

112 views

1 Answer

1 1 vote

A source vertex in a directed graph has $\text{indegree}=0$

Therefore, no other vertex has an edge entering a source.

This also means that no DFS starting from another vertex can reach a source vertex.

So every source must be discovered directly by the outer DFS procedure and must become the root of a DFS tree.

Now the question says the DFS forest contains only $1$ tree.

Therefore, it contains only one root.

Hence, the graph can have at most one source.

Also, every finite DAG has at least one source vertex.

$\therefore \text{Number of sources}=1$


Answer: A

Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes DPP | GAT...Next → · GO Classes DPP | GAT...
← Previous in category · GO Classes DPP | GAT...Next in category → · GO Classes DPP | GAT...
Position:
Show:

Related questions

1 1 vote
1 1 answer
159
159 views
GO Classes asked Aug 19
159 views
GO Classes DPP | GATE CS, DA | Algorithms | Topological Sort
Can the above graph be topologically sorted?Yes No
2 2 votes
1 1 answer
115
115 views
GO Classes asked Aug 19
115 views
GO Classes DPP | GATE CS, DA | Algorithms | Topological Ordering
Is the reverse postorder the only valid topological order for this graph?No Yes
1 1 vote
1 1 answer
98
98 views
GO Classes asked Aug 19
98 views
GO Classes DPP | GATE CS, DA | Algorithms | Distance vs Topological Order
Let $G=(V,E)$ be a dag, where each edge is annotated with some positive length. Let $s$ be a source vertex in $G$.Suppose we run Dijkstra's algorithm to compute the dista...
2 2 votes
1 1 answer
99
99 views
GO Classes asked Aug 19
99 views
GO Classes DPP | GATE CS, DA | Algorithms | Topological Ordering
Which of the following is a valid topological ordering of the vertices in the given graph?$0 \rightarrow 6 \rightarrow 1 \rightarrow 7 \rightarrow 3 \rightarrow 5 \righta...