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?

Dedra

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

Tavy

Nice thourough answer! Can you elaborate on what you mean by tree-shaped problem ? Also, how do you propose storing the path travelled by the algorithm to reach the goal as opposed to the complete traversal? – Wardship

@Wardship tree-shaped problem means the graph you are searching is a tree. And for your second question: this depends on the problem. One possibility is simply storing the path to a node together with each expanded node, if it is feasible. – Tavy

It is more formal to say that a 'single state' could be visited multiple times by a tree search, and NOT a node. As every node in search tree corresponds to a single path along the state space graph and is visited at most once by tree searches. (Albeit this is not true for Iterative Deepening Search which traverses the tree with increasing depth limits, but in that case also in every iteration every node is visited just once) – Parlin

@NaderhadjiGhanbari Whether state or node is more adequate for the vertices of the underlying problem graph, in contrast to the traversal graph, depends on the context. But using state for the problem graph vertices and node for the traversal graph could definately improve the clarity of the answer. I'll try to rewrite it soon. Thank you. – Tavy

TL;DR: graph search is using a closed data structure while tree search does not. – Eats

I disagree with the blanket statement that "graph search requires more memory" because if the state space is predetermined, you can 'remove' a state from the state space instead of copying it to a "closed" list, since both are effectively the same when choosing the next state. – Unknow

"This apparent inefficiency is sometimes wanted, as explained later". I didn't quite find the explanation for this in the answer. – Strohben

Great answer. In the graph search psuedocode, shouldn't next <- select from open come before remove next from open? – Devito

Can the tree search version of A* have a node in the frontier multiple times? – Pour

@Pour Yes, this is possible. Note that you can create many different variants of these algorithms by changing little facts. Like making tree search behave a little bit like graph search by treating the open list like a limited closed list. Not all these tweaks have names. – Tavy

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.

Fusil

Hm, the context of the question is not completely clear to me, but looking at it again after seeing your answer, @ziggystar, I do get the feeling that the mention of A* and AI indicate that you may be right, and my answer out of context. I interpreted "tree search" as "searching a tree". Not "searching a general graph using a tree-shaped traversal pattern", which is what your answer implies. – Fusil

@Fusil I've included your rephrasing in my answer. It's good for clarification. – Tavy

Added a note of this in the answer. I suspect that my answer is the right one for many people who find their way here via Google etc., even if it may be out of context for what Rayhanur Rahman was after. – Fusil

I've seen a lot of students having difficulties in studying search algorithms and your answer just misleads them. – Parlin

The question is about search algorithms, not about graph theory in general. So I'm not sure this answer contributes much here since it really doesn't distinguish between the graph fed into the search and the graph or tree created BY the search. – Automatism

The answer is about search algorithms as well, but it's true that it's not what the poster asked about. See the “Update” in the answer – I realized in March 2014 that I misunderstood the question. My reason for not deleting the answer is that it might still be useful to someone who came here via search. – Fusil

Answer 3

The only difference between a graph and a tree is cycle. A graph may contain cycles, a tree cannot. So when you're going to implement a search algorithm on a tree, you don't need to consider the existence of cycles, but when working with an arbitrary graph, you'll need to consider them. If you don't handle the cycles, the algorithm may eventually fall in an infinite loop or an endless recursion.

Another point to think is the directional properties of the graph you're dealing with. In most cases we deal with trees that represent parent-child relationships at each edge. A DAG (directed acyclic graph) also shows similar characteristics. But bi-directional graphs are different. Each edge in a bi-directional graphs represents two neighbors. So the algorithmic approaches should differ a bit for these two types of graphs.

Kerby

To add to this, if you really have tree, you don't need to do duplicate detection in A*. You'll still need a way to extract the final path, though, so you might still have a closed list. – Insnare

In normal terms, a tree is a directed graph with at most one path between any two vertices. That is, there are two differences between graphs and trees: Directed, and path uniqueness. An algorithm working on a DAG has no need to check for cycles, and an algorithm working on a tree no need to check for duplicates. – Chuddar

Terminology varies, but trees are not always taken to be directed. For a rooted tree, i.e. when one node is specified to be the root, there is an implied direction, but trees do not have to be rooted. Also, general graphs can be either directed or undirected. Furthermore, if you demand only at most one path between two vertices, you also include forests. A tree is normally defined to be a connected graph, i.e. there must be precisely one path. – Fusil

This answer gets more at the difference between trees and graphs in graph theory, but not really with the different types of search algorithms. – Automatism

Answer 4

GRAPH VS TREE

• Graphs have cycles
• Trees don't have cycles "For example imagine any tree in your head, branches don't not have direct connections to the root, but branches have connections to other branches, upward"

But in case of AI Graph-search vs Tree-search

Graph search have a good property that's whenever the algorithm explore a new node and it mark it as visited , "Regardless of the algorithm used", the algorithm typically explores all the other nodes that are reachable from the current node.

For example consider the following graph with 3 vertices A B and C, and consider the following the edges

A-B, B-C, and C-A, Well there is a cycle from C to A,

And when do DFS starting from A, A will generate a new state B, B will generate a new state C, but when C is explored the algorithm will try to generate a new state A but A is already visited thus it will be ignored. Cool!

But what about trees? well trees algorithm don't mark the visited node as visited, but trees don't have cycles, how it would get in an infinite loops?

Consider this Tree with 3 vertices and consider the following edges

A - B - C rooted at A, downward. And let's assume we are using DFS algorithm

A will generate a new state B, B will generate two states A & C, because Trees don't have "Mark a node visited if it's explored" thus maybe the DFS algorithm will explore A again, thus generating a new state B, thus we are getting in an infinite loop.

But have you noticed something, we are working on undirected edges i.e. there is a connection between A-B and B-A. of course this is not a cycle, because the cycle implies that the vertices must be >= 3 and all the vertices are distinct except the first and the last nodes.

S.T A->B->A->B->A it's not a cycle because it violates the cycling property >= 3. But indeed A->B->C->A is a cycle >= 3 distinct nodes Checked, the first and the last node are the same Checked.

Again consider the tree edges, A->B->C->B->A, of course its not a cycle, because there are two Bs, which mean not all the nodes are distinct.

Lastly you could implement a tree-search algorithm, to prevent exploring the same node twice. But that have consequences.

Deontology

This answer is confusing because it seems to mix the situation where the problem is a tree or a graph with whether the search algorithm itself uses a tree or a graph during the search. – Automatism

Answer 5

In simple words, tree does not contain cycles and where as graph can. So when we do search, we should avoid cycles in graphs so that we don't get into infinite loops.

Another aspect is tree will typically have some kind of topological sorting or a property like binary search tree which makes search so fast and easy compared to graphs.

Italianism

Answer 6

I will add to the @ziggystar's answer (other answers refer to the differences between trees and graphs as data structures, which is not what the question is about, the question refers to the tree VS graph algorithms for traversing your graph!).

This somewhat confusing terminology comes from Russell and Norvig's "Artificial Intelligence A Modern Approach":

Tree-Search algorithm - is any particular algorithm used for solving your search problem.
Graph-Search algorithm - is a Tree-Search algorithm augmented with a set of explored states.

Both of these algorithms are represented as a tree! The reason we call the Graph-Search algorithm a Graph-Search algorithm is because it can be represented (again - as a tree) directly on our search problem's graph.

---

Take a look at the map of Romania. This is our search problem's graph.

Now, we can apply many algorithms to find a path from Arad to Bucharest (Breadth-First Search, Depth-First Search, Greedy Search - anything our heart desires). All of these algorithms, however, can be divided into Tree-Search algorithms and Graph-Search algorithms.

The Tree-Search algorithm represents the solution to our Arad-to-Bucharest problem as a tree. Note the repeated "Arad" node.

The Graph-Search algorithm represents the solution to our Arad-to-Bucharest problem as a tree, too - except we remove the repeated "Arad" node from the tree. However, thanks to this removal of repeated states, we have a nicer way to represent it - directly on the graph of our search problem, on the map of Romania! Hence the "Graph" in the "Graph-Search algorithm".

---

Here is some pseudocode for you. Note that the only difference between the Tree-Search algorithm and Graph-Search algorithm is the addition of the set of explored states.

Kislev

Answer 7

You can check the slide 13 for pseudo code.

Rosariarosario