Graph traversal: Difference between revisions

Browse history interactively

← Previous edit

Content deleted Content added

VisualWikitext

Revision as of 02:23, 12 October 2024 edit JJMC89 bot III (talk \| contribs) Bots, Administrators 4,307,196 edits m Moving Category:Graph algorithms to Category:Algorithms in graph theory per Wikipedia:Categories for discussion/Log/2024 October 4#Category:Graph algorithms Tag: Reverted ← Previous edit		Latest revision as of 19:01, 4 June 2025 edit undo Headbomb (talk \| contribs) Edit filter managers, Autopatrolled, Extended confirmed users, Page movers, File movers, New page reviewers, Pending changes reviewers, Rollbackers, Template editors 472,863 edits Altered template type. Add: chapter, title. \| Use this tool. Report bugs. \| #UCB_Gadget
(One intermediate revision by one other user not shown)
Line 85: ==Universal traversal sequences== {{expand section\|date=December 2016}} A ''universal traversal sequence'' is a sequence of instructions comprising a graph traversal for any [[regular graph]] with a set number of vertices and for any starting vertex. A probabilistic proof was used by Aleliunas et al. to show that there exists a universal traversal sequence with number of instructions proportional to {{nowrap\|''O''(''n''<sup>5</sup>)}} for any regular graph with ''n'' vertices.<ref>{{cite ~~journal~~book\|last1=Aleliunas\|first1=R.\|last2=Karp\|first2=R.\|last3=Lipton\|first3=R.\|last4=Lovász\|first4=L.\|last5=Rackoff\|first5=C. \|title=20th Annual Symposium on Foundations of Computer Science (SFCS 1979) \|chapter=Random walks, universal traversal sequences, and the complexity of maze problems~~\|journal=20th~~ ~~Annual Symposium on Foundations of Computer Science (SFCS 1979)~~\|pages=218–223\|date=1979\|doi=10.1109/SFCS.1979.34\|s2cid=18719861 }}</ref> The steps specified in the sequence are relative to the current node, not absolute. For example, if the current node is ''v''<sub>''j''</sub>, and ''v''<sub>''j''</sub> has ''d'' neighbors, then the traversal sequence will specify the next node to visit, ''v''<sub>''j''+1</sub>, as the ''i''<sup>th</sup> neighbor of ''v''<sub>''j''</sub>, where 1 ≤ ''i'' ≤ ''d''. ==See also== Line 96: {{Data structures and algorithms}} [[Category:~~Algorithms~~Graph ~~in graph theory~~algorithms]] [[Category:Articles with example pseudocode]]