Q: How is graph search different from tree search?

This is actually a very important issue which is perhaps a little under-emphasized in the book. Graph search maintains in addition to its fringe (or open list) also a closed list that contains all nodes that have been expanded in the past. Note that for BFS and UCS we weren't allowed to forget those anyway. Everytime, we expand a node and put its successors into the fringe we first check whether the states of these successors were expanded before, in which case they would be on the closed list. If they are on our closed list, we do *not* put them in our fringe. So we do more work, but we cut down the search tree potentially by a lot.

For UCS, when we discover that a state has already been considered, we are guaranteed that the last discovered path to that state in our search tree must have higher path-cost. This is simply true because UCS visits nodes according to increasing path-cost. So, we can safely delete the last discovered path and still be optimal. A similar reasoning holds for BFS in case of constant step cost. However, for DFS and therefore for IDS (which uses DFS) the situation is different. In this case nodes are not expanded in order of increasing path cost and it may happen that a later discovered path is actually better. So, now we need to remember the path-costs as well, and potentially delete the first node in favor of the later one. However, in this case you will have to change not only the path cost of that node, but also the path-costs of all its descendants (since you have found a better path leading to one of their ancestors, which will reflect in their total path-costs as well). With this additional trick, IDS will be optimal for constant step-cost. However, DFS need not be optimal even with this trick.

Note that doing graph search with DFS defeats the purpose of using DFS in the first place: you will now have to keep all nodes into memory which is exactly what we wanted to avoid. There is however a very useful trick even for DFS that doesn't require more memory: check newly expanded nodes only against the list of nodes that you need to maintain in memory for DFS anyway. These are the nodes that are on the path from the root to the current node. This obviously does not require extra memory but it will avoid loops of the sort A-B-C-A-B-A- etc. In fact, a search tree will never become infinitely deep anymore!

How will the search tree change in general? This depends on the strategy you employ (remember: search trees are generated dynamically, not before you start the search). For BFS you will never generate the same state in a lower layer if it already exists in a higher layer. This need not be the case for UCS if the step-costs are not constant. For DFS checking only against nodes in your path, you may generate nodes more than ones in different branches but you will not generate the same node twice on a single path. When you do DFS with full graph search (which I not recommend because of the memory issues) it is not so clear you can even conveniently represent the search as traversing a single tree. (For instance, you may need to move entire branches from one side of the tree to another.)

As an example I would try to a few of the algorithms discussed above on the problem of figure 3.18 (left and middle).