1
$\begingroup$

First of all, there is a lot of misunderstanding about the Graph search and Tree search. The difference between these two is not about Graph and Tree. They have two different algorithms. You can find the difference in the first answer in this link: What is the difference between graph-search and tree search?.

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

Please answer if you are well informed in this subject because as you see in the above link many users have answered the question wrong (the difference between graph search and Tree search)

$\endgroup$
  • $\begingroup$ The similarity between BFS and DFS is, that both are examples for uninformed search. Some authors are promising that the algorithms have a heuristic included but if no model was used to create the datastructure it will take very long to find a node in the structure. And to the close-voters of the question: the OP has asked for a search algorithm. This topic is discussed at the university and in the literature as well. There is no reason to suppose, that he is lowering the standard. $\endgroup$ – Manuel Rodriguez Feb 17 at 17:52
  • $\begingroup$ Please help me understand the relevance of this question to AI, is it a question on algorithms or you're referring to any AI related algorithm. I don't know the answer, asking out of curiosity $\endgroup$ – Zaid Syed M Md Feb 17 at 19:06
  • 1
    $\begingroup$ Possible duplicate of What is the difference between tree search and graph search? $\endgroup$ – nbro Jul 26 at 23:29
  • $\begingroup$ @DukeZhou you should also close this question as a duplicate! $\endgroup$ – nbro Jul 30 at 20:15
0
$\begingroup$

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

$\endgroup$
  • $\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
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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