Does lexicographic mean sorting node names?

No. It means comparing labels built from the search history.

Is the ordering always unique?

No. Initial choices and ties can permit different valid orders.

Does reversed LexBFS always give a perfect elimination order?

It does for chordal undirected graphs under the standard result, not for every graph.

AI Glossary / Graphs and symbolic AI / Intermediate

Lexicographic breadth-first search

Definition

Lexicographic breadth-first search, or LexBFS, is a graph traversal that orders vertices using lexicographic labels based on previously visited neighbors. It refines breadth-first search by using more information to break ordering choices. The labels describe search history; the method is not simply breadth-first search with vertex names sorted alphabetically.

What it means

In an ordinary unweighted breadth-first traversal, vertices are explored in distance layers from a starting vertex, but many choices within a layer may remain. LexBFS uses the pattern of adjacency to earlier selected vertices to distinguish such choices.
The result is a vertex ordering that is useful in structural graph algorithms. For example, on a chordal undirected graph, reversing a LexBFS discovery order yields a perfect elimination ordering. This special property does not hold for arbitrary graphs. A traversal order by itself is not a business ranking or a measure of node importance.

How it works

One explanatory implementation gives every unvisited vertex an initially empty sequence label. Select a vertex with a lexicographically largest label, using a chosen rule for ties. Then append the current descending search number to the labels of its still-unvisited neighbors.
Compare sequences from the beginning: the first unequal entry determines which is larger, with a longer sequence larger than its identical prefix under the usual convention. An efficient implementation can maintain an ordered partition and refine its groups rather than repeatedly comparing long labels. With suitable sparse graph structures, LexBFS can run in time proportional to the number of vertices plus edges.

Three practical examples

A graph-analysis library uses LexBFS ordering as part of a chordal-graph recognition or elimination-ordering procedure.
A teaching tool displays how adjacency to previously selected vertices changes the priority among unvisited vertices.
A structural graph algorithm uses ordered partition refinement to avoid an expensive repeated scan of all label sequences.

Think of it this way

Think of sorting candidates by a sequence of priority marks awarded in successive rounds, where earlier marks take precedence over later ones. The analogy is limited because LexBFS marks come from graph adjacency and a precisely defined update rule, not subjective merit or the spelling of a candidate's name.

Worked example

Consider an invented simple undirected graph with vertices A, B, C, D, and E, and edges AB, AC, BD, CD, and CE. Start at A and use descending update numbers 5, 4, 3, 2, 1. Break the first tie in favor of B.
After selecting A, its unvisited neighbors B and C each receive label [5]. D and E remain empty. Select B from the tie. Its unvisited neighbor D receives [4], while C still has [5]. Because [5] is lexicographically larger than [4], C is selected next.
Selecting C appends 3 to D's label and gives E label [3]. The remaining labels are D = [4, 3] and E = [3]. D is selected first because its initial label entry 4 exceeds 3. E is last. The discovery order is A, B, C, D, E.
The example's distance layers are {A}, {B, C}, and {D, E}, consistent with breadth-first exploration. The choice of D before E reflects its earlier adjacency history, not a rule that the letter D precedes E. Renaming the vertices while preserving the same initial and tie choices would preserve the structural behavior. Different valid tie choices can produce a different LexBFS ordering.

Illustrative case study

In a fictional graph project, Spruce Links implements “lexicographic BFS” by sorting neighbor names and using an ordinary queue. The resulting order looks plausible on small examples but fails the requirements of a downstream structural algorithm.
The developers implement the documented label or partition-refinement rule and add examples that distinguish search-history priorities from alphabetical order. This invented case illustrates an algorithm-definition error. It does not claim that alphabetical BFS is useless, only that it is a different procedure with different guarantees.

Common misconceptions and mistakes

LexBFS is not ordinary BFS with alphabetical tie-breaking. The lexicographic comparison concerns dynamically constructed labels. It is also distinct from lexicographic depth-first search, which uses a different label-update convention.
Do not reverse a LexBFS order on an arbitrary graph and assume it is a perfect elimination ordering; the relevant chordal-graph condition must hold or be checked. Also, a simple label-based implementation does not automatically achieve linear runtime. That bound requires appropriate data structures. Graph direction, loops, and multiple-edge handling should be checked in the chosen library rather than assumed from the algorithm's name.

Business use

The direct value is in graph-processing infrastructure rather than a standalone managerial decision. A business application may benefit indirectly when its graph algorithms need efficient structural ordering or recognition routines.
Document the graph type and the ordering convention expected by downstream code. Verify whether a library returns discovery order or its reverse, and record starting-vertex and tie behavior if reproducibility matters. Test the property the application needs instead of assuming that any plausible traversal order is interchangeable. This is especially important when the order supports a later correctness claim.

Check your understanding

Why is C selected before D after B in the worked example?

Answer: C has label [5], while D has [4]. Lexicographic comparison favors the earlier, larger first entry, so C remains ahead even though D was just updated.

Related terms

Breadth First Search
Sparse graph
partition refinement
chordal graph
perfect elimination ordering
graph traversal
lexicographic order
vertex ordering

Learn next

Repeat the worked example with C selected before B in the first tie. Track every label and compare the resulting order. Then distinguish discovery order from reverse order before studying the perfect-elimination property on a chordal example.

Sources

Sources: SageMath, official Graph traversals documentation, lex_BFS and label-update conventions: https://doc.sagemath.org/html/en/reference/graphs/sage/graphs/traversals.html

Previous: Lexico-syntactic pattern Next: Lexicographic max-min optimization