What is the term for the tree (or a part of the tree) of all possible paths in a graph that start from a given (source) vertex?

This is the tree that is implicitly or explicitly constructed when doing shortest path search. It appears, for example, in a lecture on search of an MIT Artificial Intelligence course, but I didn't understand if it has a name.

This is not a search tree and not really a decision tree.

Mathematically, it is a covering tree, but is there a more appropriate term in the context of shortest path search?


It's the self-avoiding walk tree (SAW tree).

The trees seem to have been first considered by C.D. Godsil (Matchings and Walks in Graphs, Journal of Graph Theory 5(3):285–297, 1981; DOI link; just before Lemma 2.4), though Godsil doesn't use the name.

(And, yes, "self-avoiding walk" is just a mighty-long way of saying "path".)

  • $\begingroup$ This does not look like a special term with a specific meaning. Of course a tree is a tree, and if it consists of self-avoiding walks, it is a tree of self-avoiding walks, or self-avoiding walk tree. I've found out that The Handbook of Artificial Intelligence by Avron Barr and Edward Feigenbaum also uses search tree term, so i will probably stick with search tree. $\endgroup$ – Alexey Mar 19 '19 at 14:14
  • 1
    $\begingroup$ Huh? You asked for a term for the trees you describe in the question. I gave you a specific term with that specific meaning. Perhaps it's not the term that is used in the community you're working with, but it is a specific answer to your question, and not some generic term that applies to anything at all. $\endgroup$ – David Richerby Mar 19 '19 at 14:20
  • $\begingroup$ Sorry, i meant rather special term for the specific meaning, but self-avoiding walk tree seems to be just a combination of self-avoiding walk and tree. For example, google only finds 368 pages with "self-avoiding walk tree" in them (quoted)... $\endgroup$ – Alexey Mar 19 '19 at 14:27
  • $\begingroup$ Probably I should have added that i was interested in this object in the context of path search in a graph. $\endgroup$ – Alexey Mar 19 '19 at 14:30
  • $\begingroup$ By the way, Wikipedia currently defines self-avoiding walk chiefly for latices, and the term is not found in their Glossary of graph theory terms... $\endgroup$ – Alexey Mar 20 '19 at 15:42

I've discovered that Nils Nilsson in Principles of Artificial Intelligence (1982) calls it just a search tree, and search tree is also used in The Handbook of Artificial Intelligence (1981) by Avron Barr and Edward Feigenbaum. I've also found a sufficiently recent paper Predicting the size of IDA*ʼs search tree (2013).

I will stick with search tree.


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.