9
$\begingroup$

I have read various answers to this question at different places, but I am still missing something.

What I have understood is that a graph search holds a closed list, with all expanded nodes, so they don't get explored again. However, if you apply breadth-first-search or uniformed-cost search at a search tree, you do the same. You have to keep the expanded nodes in memory.

$\endgroup$
5
$\begingroup$

There is always a lot of confusion about this concept, because the naming is misleading, given that both tree and graph searches produce a tree while exploring the search space, which is usually represented as a graph. The other answers are currently incorrect.

Differences

Firstly, we have to understand that the underlying problem (or search space) is almost always represented as a graph. So, the difference is not whether the problem is a tree (a special kind of graph), or a general graph!

The distinction is, instead, how we are traversing the search space (represented as a graph) to search for our goal state and whether we are using an additional list (called the closed list) or not.

So, the basic differences are

  1. In the case of a graph search, we use a list, called the closed list (also called explored set), to keep track of the nodes that have already been visited and expanded, so that they are not visited and expanded again.

  2. In the case of a tree search, we do not keep this closed list. Consequently, the same node can be visited multiple (or even infinitely many) times, which means that the produced tree (by the tree search) may contain the same node multiple times.

Advantages and disadvantages

The advantage of graph search obviously is that, if we finish the search of a node, we will never search it again, while we may do so in a tree search. The disadvantage of graph search is that it uses more memory, which we may or may not have.

So, there is a trade-off between space and time when using graph search as opposed to tree search (or vice-versa).

References

See section 3.3 (page 77) of the book Artificial Intelligence: A Modern Approach (3rd edition) by Stuart J. Russell and Peter Norvig.

$\endgroup$
  • $\begingroup$ tbh, I can't see why the other answers are not correct. You simply re-state what I have said in my answer. $\endgroup$ – Oliver Mason Dec 17 '18 at 9:11
  • 2
    $\begingroup$ I am not sure how your answer and my answer are the same, or even similar. For example, your answer starts as "Strictly speaking they're the same". My answer actually suggests that they are quite different. The code of graph search and tree search (or pseudocode), is quite distinct. $\endgroup$ – Amrinder Arora Dec 18 '18 at 20:04
  • $\begingroup$ Where is your source of information for the definition of "Tree Search" versus "Graph Search" because I think everybody's distinction's mentioned so far are wrong to some degree? My understanding of tree is that trees are not only a form of directed graph but the nodes are ORDERED, making the tree unique from a graph. Because a tree is ordered, there are no loops. Thus, a node shouldn't ever appear as multiple different nodes of the tree unless the implementer did something very wrong, because keeping track of the list of nodes visited is implicit as part of tree traversal algorithms. $\endgroup$ – Dunk Dec 18 '18 at 21:04
  • $\begingroup$ This is in most of the AI textbooks, usually the early chapters. For example, the standard text by Russell and Norvig covers this in chapter 3, around the page 90. $\endgroup$ – Amrinder Arora Dec 18 '18 at 21:45
  • $\begingroup$ @Dunk What do you mean by "a tree is ordered"? Not all trees necessarily have their elements ordered. There are trees, like red-black trees (or, in general, binary search trees), that maintain a certain order of their stored elements, but not all tress maintain a certain order of their elements. So, a tree has no loops not because it is ordered, but because there are no cycles (of the form A -> B -> A). The currently most upvoted answer ai.stackexchange.com/a/6427/2444 is wrong. $\endgroup$ – nbro Nov 10 at 22:41
5
$\begingroup$

Strictly speaking, a tree is a graph, but one which among other criteria is minimally connected (only one path between any two nodes) and acyclic (ie no loops).

Tree search, also known as tree traversal, visits each node in a tree structure exactly once. There are different orders in which the nodes are visited depending on the type of search (breadth-first vs depth-first).

Graph search is the same, generalised for any graphs (trees are, as mentioned above, a special kind of graph). Because general graphs are not necessarily minimally connected, one needs to keep track of which nodes have been visited before, which increases the computational complexity.

So, for searching, algorithms operating on trees can make a certain set of assumptions which allow optimisations not possible on a generalised graph. For example, for tree traversal you know you will visit each node only once (due to the minimal connectivity), but for other graphs you need to keep track of visited nodes if you don't want to process them multiple times (as there could be multiple paths leading to the same nodes).

Well-known graph search algorithms include A* and Dijkstra's algorithm.

$\endgroup$
  • 1
    $\begingroup$ Sorry, this answer is not correct - tree is a graph, but tree search vs. graph search is not about the structure of the underlying problem. $\endgroup$ – Amrinder Arora Dec 16 '18 at 19:52
  • 1
    $\begingroup$ I think that this answer does not provide any insight into the difference between tree and graph searches, so this does not answer the actual question. Yes, a tree is a graph. Why should this help to differentiate the two? $\endgroup$ – nbro Jul 26 at 21:02
  • 1
    $\begingroup$ @nbro Have you even read the second paragraph? $\endgroup$ – Oliver Mason Jul 27 at 14:32
  • 1
    $\begingroup$ @OliverMason Yes, of course. What does that have to do with tree search and graph search? By the way, the information (e.g. For example, for tree traversal you know you will visit each node only once (due to the minimal connectivity)) in the second paragraph is wrong. This is not the usual definition of tree and graph searches. You generalized badly. Have a look at book: AI: Modern Approach. It is so sad that you received so many upvotes for this answer. It really means that often upvotes are not a synonym for quality. $\endgroup$ – nbro Jul 27 at 14:34
  • 2
    $\begingroup$ @DukeZhou Yeah, the names are a bit confusing. TreeSearch is not "Search algorithm that runs on a tree" but "A search algorithm that can work on trees or on graphs, but which makes a specific decision that might cause it to fail on some non-tree graphs". Graph search is not "Search algorithm that runs on a graph", but "A search algorithm that can work on trees or on graphs, but that makes a specific decision that makes it slower and more memory intensive than TreeSearch, but certain to work on all non-tree graphs." Because of this, you might choose to run TreeSearch even on a non-tree Graph. $\endgroup$ – John Doucette Nov 12 at 21:15
-1
$\begingroup$

Expanding from the answer that @Oliver Mason gave, they are both graphs but only that a tree graph is a special case scenario.
The main difference is in the search pattern that is used to search through the graph.
Difference:

  • Graph search uses more memory because it stores all the cycles of the tree
$\endgroup$

protected by nbro Jul 26 at 20:59

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.