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 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 Donald J. Rose, Robert E. Tarjan, and George S. Lueker (1976). A more detailed survey of the topic is presented by Corneil (2004). 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:

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 the rule:

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. In lexicographic breadth-first search, the output ordering is the order that would be produced by the rule:

So, when two vertices v and w have the same earliest predecessor, earlier than any other unchosen vertices, the standard breadth-first search algorithm will order them arbitrarily. Instead, in this case, the LexBFS algorithm would choose between v and w by the output ordering of their second-earliest predecessors. If only one of them has a second-earliest predecessor that has already been output, that one is chosen. If both v and w have the same second-earliest predecessor, then the tie is broken by considering their third-earliest predecessors, and so on.

...
Wikipedia