**Is the answer to problem 4 'a : the number of nodes', because at the end of the search, all the nodes will be in explored? 

 **I don't understand why the the maximum amount of storage isn't the number of nodes. At the end of the search for a worst case scenario, all of the nodes would be explored eventually.

 **When searching by dfs, the program visits the node to see what edges are related to it, then it explores that node. I don't know why 'a' would be wrong

Please help, thank you!

kevinmowers@yahoo.com wrote:

4. Not counting the graph itself, the stack used to keep track of subprogram calls, the explored set, or the visited list, the maximum amount of non-local storage needed for Graph.search doing BFS is

 the number of nodes
 the number of edges
 the maximum number of neighbors for any one node
 0

**Is the answer to problem 4 'a : the number of nodes', because at the end of the search, all the nodes will be in explored? 

Both this question and the next are asking about the storage used to keep track of the nodes to be explored next. In BFS you keep track of the neighbors. They are put into the queue. At worst, all the nodes could be in that queue.

 

5. Not counting the graph itself, the stack used to keep track of subprogram calls, the explored set, or the visited list, the maximum amount of non-local storage needed for Graph.search doing DFS is

 the number of nodes
 the number of edges
 the maximum number of neighbors for any one node
 0

 **I don't understand why the the maximum amount of storage isn't the number of nodes. At the end of the search for a worst case scenario, all of the nodes would be explored eventually.

It is the number of nodes. It's not because all the nodes will be explored eventually but because almost all the nodes might be neighbors of a single line descent to the bottom of the tree.

 

6. Not counting the graph itself, the stack used to keep track of subprogram calls, the explored set, or the visited list, the maximum amount of non-local storage needed for Graph.dfs (the recursive version of depth-first-search) is

 the number of nodes
 the number of edges
 the maximum number of neighbors for any one node
 0

**I got this right, but I don't understand why it would be 0

 

It's 0 because recursive DFS doesn't keep a record of  the nodes to be explored next.

 

7. The code for Graph.dfs must include both of the following lines. 

visited.add(n);  // line a

and

explored.add(n); // line b

In the code, 

 line a must precede line b
 line b must precede line a
 either line a or line b can come first
 neither line a nor line b can come first

 **When searching by dfs, the program visits the node to see what edges are related to it, then it explores that node. I don't know why 'a' would be wrong

Please help, thank you!

This was mentioned a while ago