The depth-first search algorithm described in Listing 28.8 uses recursion. Design a new algorithm without using recursion. Describe it using pseudocode. Implement it by defining a new class named UnweightedGraphWithNonrecursiveDFS that extends UnweightedGraph and overriding the dfs method.

Listing

1 Tree dfs(vertex v) { visit v; for each neighbor w of v if (w has not been visited) { set v as the parent for w in the tree; dfs (w); 8 }