In breadth-first and depth-first search, an undiscovered node is marked discover

Question

In breadth-first and depth-first search, an undiscovered node is marked discovered when it is first encountered, and marked processed when it has been completely searched. At any given moment, several nodes might be simultaneously in the discovered state.
(a) Describe a graph on n vertices and a particular starting vertex v such that ?(n) nodes are simultaneously in the discovered state during a breadth-first search starting from v.
(b) Describe a graph on n vertices and a particular starting vertex v such that ?(n) nodes are simultaneously in the discovered state during a depth-first search starting from v.
(c) Describe a graph on n vertices and a particular starting vertex v such that at some point ?(n) nodes remain undiscovered, while ?(n) nodes have been processed during adepth-first search starting from v. (Note, there may also be discovered nodes.)

Explanation / Answer

(a) A graph with n vertices and a depth of one where no node was processed yet which started at the root.
(b) A graph with n vertices and a depth of n where no node was processed yet which started at the root.
(c) E.g. the graph of (b) which is processed up to n/2.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.