Maze-solving algorithm: Difference between revisions

Revision as of 21:39, 30 September 2016

Revision as of 05:54, 3 November 2016

Line 37:

In this case each path is walked down exactly twice, once in each direction. The resulting [[Glossary of graph theory#Walks|walk]] is called a bidirectional double-tracing.<ref name="Eulerian Graphs and related Topics">H. Fleischner: ''Eulerian Graphs and related Topics.'' In: ''Annals of Discrete Mathematics'' No. 50 Part 1 Volume 2, 1991, page X20.</ref>

Essentially, this algorithm, which was discovered in the 19th century, has been used about a hundred years later as [[depth-first search]].<ref>{{citation|title=Graph Algorithms|first=Shimon|last=Even|authorlink=Shimon Even|edition=2nd|publisher=Cambridge University Press|year=2011|isbn=978-0-521-73653-4|pages=46–48|url=httphttps://books.google.com/books?id=m3QTSMYm5rkC&pg=PA46}}.</ref><ref>{{citation|title=Algorithms in C++: Graph Algorithms|first=Robert|last=Sedgewick|edition=3rd|publisher=Pearson Education|year=2002|isbn=978-0-201-36118-6}}.</ref>

== Dead-end filling ==