Go backward to 3 Comparting Different Search Strategies
Go up to Top
Go forward to 5 Arc Consistency

4 Generating Graphs Good for Different Search Strategies

For each of the following, give a graph that is a tree (there is at most one arc into any node), contains at most 15 nodes, and has at most two arcs out of any node.

Give a graph where depth-first search is much more efficient (expands fewer nodes) than breadth-first search.
Give a graph where breadth-first search is much better than depth-first search.
Give a graph where A^* search is more efficient than either depth-first search or breadth-first search.
Give a graph where depth-first search and breadth-first search are both more efficient than A^* search.

You must draw the graph and show the order of the neighbours (this is needed for the depth-first search). Either give the arc costs and heuristic function or state explicitly that you are drawing the graph to scale and are using Euclidean distance for the arc costs and the heuristic function.

Solution to generating graphs