This question already has an answer here:

First of all, there is a lot of misunderstanding about the graph search and tree search. The difference between these two is not about graphs and trees. They have two different algorithms. You can find the difference in this answer to the question What is the difference between graph-search and tree search?.

Now, I want to be sure that I have understood these two searches well. We have a graph search and a tree search for each searching algorithm. For example, BFS graph search and BFS tree search. Or DFS graph search and DFS tree search (DFS tree search is not complete, for example). Iterative deepening graph search and iterative deepening tree search. Is this correct?


marked as duplicate by nbro, Manuel Rodriguez, John Doucette, DukeZhou Nov 14 at 20:48

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.


As you found the difference between tree search and graph search is in their traversing approach which is a tree or graph and not related to the traversing space which can be tree or space. Hence, because of the structure of a tree, both graph and tree search algorithms could reach the same result, and the difference of these algorithms could be distinguishable over traversing on a general graph.

In sum, BFS and DFS are creating a tree from traversing a graph and they are tree search algorithm. Although some nodes of that tree could point to the same node in the real basis graph (which is traversed by these algorithms).

  • $\begingroup$ related to the last paragraph of your answer: so we can use DFS graph search algorithm by saving the visited nodes so they are not just a tree search algorithm. $\endgroup$ – jack.math Feb 18 at 11:20
  • $\begingroup$ This answer is wrong. Both tree and graph searches produce a tree (but the tree search may revisit a state multiple times, while this does not happen in the graph search)! In practice, it means that you may see the same state multiple times in the tree produced by the tree search. See this answer ai.stackexchange.com/a/9554/2444, which was also wrong, but I corrected it (for the good of the community!). $\endgroup$ – nbro Nov 10 at 23:27

First of all every tree is a graph but every graph is not must to be considered as tree. Difference lies in their Transversal pattern for searching, algorithms operating on trees can make a certain set of assumptions which allow situation not possible on a generalised graph. For example, while traversing tree you will visit each node only once (only 1 path), but in graphs you need to keep track of visited nodes if you don't want to process them multiple times (multiple paths). Transversing a graph they create a tree


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