6
$\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$

Strictly speaking they're the same: 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).

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).

$\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
  • $\begingroup$ Great answer--concise and clear. (I might add that trees are a form of directed graph.) $\endgroup$ – DukeZhou Dec 16 '18 at 22:29
  • $\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
  • $\begingroup$ @nbro Have you even read the second paragraph? $\endgroup$ – Oliver Mason Jul 27 at 14:32
  • $\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
0
$\begingroup$

There is always a lot of confusion about this concept. (And the naming does not help!). The other answers present so far are not correct.

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 instead is how we are traversing to search for our goal state. It also includes whether we are using a list or array (often called the closed list) or not.

So, the basic differences are

  1. If doing graph search, keep a "closed" list, that is, a list of nodes where the search has been completed.

  2. If doing a tree search, we don't keep this closed list.

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 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).

Now, about the naming.

Graph Search is called graph search, because when we observe the traversal structure, we observe a GRAPH, that this node leads us to the other node that we saw before, etc, etc.

Tree search is called a tree search, because when we observe the traversal structure, we observe a TREE. We observe a tree, even if the underlying problem structure is a graph. This is because when we observe a node, we have no recollection of having seen it earlier, we don't store that list, etc. So, the same node in the underlying problem structure can appear as multiple times (as different nodes) of the tree.

$\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
  • 1
    $\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
-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.