Lexicographic breadth-first search

In computer science, lexicographic breadth-first search or Lex-BFS is a linear time algorithm for ordering the vertices of a graph. The algorithm is different from a breadth-first search, but it produces an ordering that is consistent with breadth-first search. The lexicographic breadth-first search algorithm is based on the idea of partition refinement and was first developed by . A more detailed survey of the topic is presented by . It has been used as a subroutine in other graph algorithms including the recognition of chordal graphs, and optimal coloring of distance-hereditary graphs. The breadth-first search algorithm is commonly defined by the following process: Initialize a queue of graph vertices, with the starting vertex of the graph as the queue's only element. While the queue is non-empty, remove (dequeue) a vertex v from the queue, and add to the queue (enqueue) all the other vertices that can be reached by an edge from v that have not already been added in earlier steps. However, rather than defining the vertex to choose at each step in an imperative way as the one produced by the dequeue operation of a queue, one can define the same sequence of vertices declaratively by the properties of these vertices. That is, a standard breadth-first search is just the result of repeatedly applying this rule: Repeatedly output a vertex v, choosing at each step a vertex v that has not already been chosen and that has a predecessor (a vertex that has an edge to v) as early in the output as possible. In some cases, this ordering of vertices by the output positions of their predecessors may have ties — two different vertices have the same earliest predecessor. In this case, the order in which those two vertices are chosen may be arbitrary. The output of lexicographic breadth-first search differs from a standard breadth-first search in having a consistent rule for breaking such ties.