The depth-first search algorithm described in Listing 28.8, Depth-First Search Algorithm, 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. Write a test program same as Listing 28.9, TestPFS.java, except that UnweightedGraph is replaced by UnweightedGraphWithNonrecursiveDFS.

Data from Listing 28.8,

Data from Listing 28.9,

Input: G = (V. E) and a starting vertex v Output: a DFS tree rooted at v 1 SearchTree dfs (vertex v) { 2 visit v: for each nei ghbor w of v 1f (w has not been visited) { set v as the parent for w in the tree;: dfs (w) : 3 4 6 8 }