Graph traversal: Difference between revisions

Revision as of 17:23, 1 February 2017

Revision as of 14:12, 11 February 2017

Line 41:

{{main|Breadth-first search}}

{{expand section|date=October 2012}}

A breadth-first search (BFS) is another technique for traversing a finite graph. BFS visits the neighbor vertices before visiting the child vertices, and a [[Queue_Queue (abstract_data_typeabstract data type)|queue]] is used in the search process. This algorithm is often used to find the shortest path from one vertex to another.

====Pseudocode====

Line 84:

==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 <math display="inline">O\left(n^5\right)</math> for any regular graph with ''n'' vertices.<ref>{{cite journal|last1=Aleliunas|first1=R.|last2=Karp|first2=R.|last3=Lipton|first3=R.|last4=Lovász|first4=L.|last5=Rackoff|first5=C.|title=Random walks, universal traversal sequences, and the complexity of maze problems|journal=20th Annual Symposium on Foundations of Computer Science (sfcs 1979)|date=1979|doi=10.1109/SFCS.1979.34}}</ref> The steps specified in the sequence are

relative to the current node, not absolute. For example, if the current node is v_j, and v_j has ''d'' neighbors, then the traversal sequence will specify the next node to visit, v_j+1, as the ''i''^th neighbor of v_j, where 1 ≤ ''i'' ≤ ''d''.