What is the difference between graph search and tree search?

Question

What is the difference between graph search and tree search versions regarding DFS, A* searches in artificial intelligence?

Answer 1

Judging from the existing answers, there seems to be a lot of confusion about this concept.

The Problem Is Always a Graph

The distinction between tree search and graph search is not rooted in the fact whether the problem graph is a tree or a general graph. It is always assumed you're dealing with a general graph. The distinction lies in the traversal pattern that is used to search through the graph, which can be graph-shaped or tree-shaped.

If you're dealing with a tree-shaped problem, both algorithm variants lead to equivalent results. So you can pick the simpler tree search variant.

Difference Between Graph and Tree Search

Your basic graph search algorithm looks something like the following. With a start node start, directed edges as successors and a goal specification used in the loop condition. open holds the nodes in memory, which are currently under consideration, the open list. Note that the following pseudo code is not correct in every aspect (2).

Tree Search

open <- [] next <- start  while next is not goal {     add all successors of next to open     next <- select one node from open     remove next from open }  return next 

Depending on how you implement select from open, you obtain different variants of search algorithms, like depth-first search (DFS) (pick newest element), breadth first search (BFS) (pick oldest element) or uniform cost search (pick element with lowest path cost), the popular A-star search by choosing the node with lowest cost plus heuristic value, and so on.

The algorithm stated above is actually called tree search. It will visit a state of the underlying problem graph multiple times, if there are multiple directed paths to it rooting in the start state. It is even possible to visit a state an infinite number of times if it lies on a directed loop. But each visit corresponds to a different node in the tree generated by our search algorithm. This apparent inefficiency is sometimes wanted, as explained later.

Graph Search

As we saw, tree search can visit a state multiple times. And as such it will explore the "sub tree" found after this state several times, which can be expensive. Graph search fixes this by keeping track of all visited states in a closed list. If a newly found successor to next is already known, it won't be inserted into the open list:

open <- [] closed <- [] next <- start  while next is not goal {     add next to closed     add all successors of next to open, which are not in closed      remove next from open     next <- select from open }  return next 

Comparison

We notice that graph search requires more memory, as it keeps track of all visited states. This may compensated by the smaller open list, which results in improved search efficiency.

Optimal solutions

Some methods of implementing select can guarantee to return optimal solutions - i.e. a shortest path or a path with minimal cost (for graphs with costs attached to edges). This basically holds whenever nodes are expanded in order of increasing cost, or when the cost is a nonzero positive constant. A common algorithm that implements this kind of select is uniform cost search, or if step costs are identical, BFS or IDDFS. IDDFS avoids BFS's aggressive memory consumption and is generally recommended for uninformed search (aka brute force) when step size is constant.

A*

Also the (very popular) A* tree search algorithm delivers an optimal solution when used with an admissible heuristic. The A* graph search algorithm, however, only makes this guarantee when it used with a consistent (or "monotonic") heuristic (a stronger condition than admissibility).

(2) Flaws of pseudo-code

For simplicity, the presented code does not:

• handle failing searches, i.e. it only works if a solution can be found

Answer 2

A tree is a special case of a graph, so whatever works for general graphs works for trees. A tree is a graph where there is precisely one path between each pair of nodes. This implies that it does not contain any cycles, as a previous answer states, but a directed graph without cycles (a DAG, directed acyclic graph) is not necessarily a tree.

However, if you know that your graph has some restrictions, e.g. that it is a tree or a DAG, you can usually find some more efficient search algorithm than for an unrestricted graph. For example, it probably does not make much sense to use A*, or its non-heuristic counterpart “Dijkstra's algorithm”, on a tree (where there is only one path to choose anyway, which you can find by DFS or BFS) or on a DAG (where an optimal path can be found by considering vertices in the order obtained by topological sorting).

As for directed vs undirected, an undirected graph is a special case of a directed one, namely the case that follows the rule “if there is an edge (link, transition) from u to v there is also an edge from v to u.

Update: Note that if what you care about is the traversal pattern of the search rather than the structure of the graph itself, this is not the answer. See, e.g., @ziggystar's answer.