“字典序广度优先搜索进一步比较全部已选邻居历史，而不只保留首次发现的队列位置；并列块按新邻域逐次精化。在边ab、ad、bc、be、de上，普通BFS允许a,b,d,c,e，字典序历史却要求e先…”
形式陈述
先约定标签方向
输入是顶点为0,…,n−1的有限简单无向图，没有自环或平行边。开始时所有顶点未选，标签均为空序列。第t轮从0开始：选择标签字典序最大的未选顶点v，把v记入搜索序σ；随后对每个未选邻居，把整数n−t追加在标签末尾。
每个标签因此是严格递减的整数序列。字典序先比较第一处不同项，数大者优先；若一个序列是另一个的真前缀，较长者优先。例如 [6,4] > [6,3] > [6] > [5,4,3] > []。标签相同可以任意选择，但应记录实际并列规则以便重放。
算法输出全部n个顶点的排列。对弦图，反序π=reverse(σ)一定是完美消去序：每个顶点在π中排在它后面的邻居两两相邻。一般图也有搜索序，只是反序可能不满足这个条件。[1, PDF pp.10–16]
直觉
当前邻居只在原来的并列组里优先
第一轮选v后，所有邻居得到标签[n]，排在空标签之前。第二轮的新数n−1比此前任何数都小，因此只能打破原来相同标签之间的并列；它不能推翻第一处已有差异。一个刚更新的低优先块，不能整体跑到此前的高优先块前面。
利用有序划分精化，用一个块保存同标签顶点，块按标签从大到小排列。取第一块里的元素作为v；移除v，再用v的未选邻居精化所有触及块。每块的邻居交集在前，非邻居余集在后。初始化只有一个全体顶点块，归纳可得每轮维护的正是概念标签次序。
python
part = OrderedPartition(n)
order = []
for _ in range(n):
v = part.pop_first()
order.append(v)
part.refine(u for u in adj[v] if part.owner[u] is not None)代码核心不真的构造长标签。附件块内链初始按编号，交块按当前邻接列表首次出现的顺序排列，所以并列选择受输入邻接次序影响。任意合法并列都保持定理；不同次序并不要求给出同一排列。
为何弦图不容许一个坏的反序
把搜索反序编号为α:V→{1,…,n}，所以实际搜索从编号n向1选择。假设反序不是完美消去序。存在三点无弦路径x,v,y，其中α(v)小于两端编号。更一般地，考虑所有无弦路径
使端点编号都大于内部编号；把编号较小的端点放在u₀，并令i=α(u₀)。刚才的三点路径保证这种路径存在。选一个i尽可能大的例子。于是α(uᵣ)>i，所有内部编号<i。
在算法选择u₀的时刻，编号>i的顶点已经选过。记S为u₀在这些已选顶点中的邻居。无弦路径长度至少2，u₀不邻接uᵣ，所以uᵣ∉S。
取任意z∈S。先证明z邻接uᵣ：否则在路径中取与z相邻的最后一个uⱼ；至少u₀满足。路径z,uⱼ,…,uᵣ仍无弦，两个端点编号均>i，内部编号至多i，给出更大的较小端点编号，违背i的选择。
再证明z邻接uᵣ₋₁：若不相邻，在u₀,…,uᵣ₋₁中取最后一个与z相邻的uⱼ，必有j≤r−2。z,uⱼ,…,uᵣ,z构成至少四点的无弦圈：原路径内部无弦，而z除了这段的两端外没有邻接点。这与图是弦图矛盾。
所以S中每个顶点都是uᵣ₋₁的已选邻居，而且uᵣ₋₁还邻接已经选过的uᵣ，后者不在S中。uᵣ₋₁的已选邻居集合严格包含u₀的集合。按递减编号列出这两个集合，第一项额外出现的编号使前者标签更大；若没有中途差异，则后者是前者的真前缀，同样前者更大。uᵣ₋₁此时尚未选，算法不可能舍弃它而选择u₀，得到矛盾。
这个证明只用了“已选邻居集合严格包含时标签必更大”，没有假定并列取最小编号。路径极值思路来自[2, §2.4]对最大基数搜索的证明；这里用标签严格包含推出字典序选择的矛盾。
例子与边界
六点图的块轨迹
取边01、02、12、23、04、14、45，按此顺序建立两向邻接表。初始块为 [0,1,2,3,4,5]。附件得到：
| 选中的顶点 | 选择并精化后的块序列 |
|---|---|
| 0 | [1,2,4]；[3,5] |
| 1 | [2,4]；[3,5] |
| 2 | [4]；[3]；[5] |
| 4 | [3]；[5] |
| 3 | [5] |
| 5 | 空 |
因此σ=[0,1,2,4,3,5]，π=[5,3,4,2,1,0]。选2之后，4保持在3之前：4在第一轮已经得到6，而3此时才得到4。把所有当前邻居一律推到队首，会错误地让3越过4。
普通BFS的并列还不够细
取边ab、ad、bc、be、de。普通广度优先搜索允许序列a,b,d,c,e：b先发现c、e，后续d不会改动它们的队列次序。LexBFS在选a,b,d之后，却必须让e先于c，因为二者都见过b，只有e又见过d。因此a,b,d,e,c合法，而前一个BFS序不合法。
这里的“字典序”比较的是邻接历史，不是顶点名字。按字母顺序扫描每份邻接表，只规定普通BFS的局部并列，不能自动实现LexBFS。
失败的排序与失败的图
无弦四圈01、12、23、30可得到σ=[0,1,3,2]，反序[2,3,1,0]中，顶点2的更晚邻居3和1不相邻，违反完美消去条件。由于刚才已证明弦图上每次LexBFS都成功，这一次失败足以判定图非弦。
换成三点路径0—1—2，随意给出的顺序[1,0,2]也失败，但这张图是弦图，它有完美消去序[0,2,1]。所以必须同时记录“候选确由LexBFS得到”与“候选未通过检查”，不能让任意坏排序单独充当非弦证据。
非连通图不需要特殊失败出口：一个分量处理完后，余下顶点重新在空历史块里并列。孤立顶点可在相应轮被取出；空图输出空排列。
推论与应用
线性的是搜索核心，不是全部调试输出
在已准备好的无重复邻接表上，每个顶点取出一次，每份邻接记录扫描一次。无向边uv只有较早选择的端点会把仍活动的另一端放进精化集合，所以总移动次数恰为m。精化有n次基本调用成本，故单位成本RAM下时间O(n+m)，辅助空间O(n)。连同输入邻接表，总空间O(n+m)。
从任意边列表检查自环、重复无向边并建立邻接表，附件另用哈希集合完成，期望O(n+m)。这段输入校验与已经准备好邻接表时的确定性线性核心分开。record_trace=True会在每轮枚举完整分区，最坏另有O(n²)时间和输出空间；关闭轨迹不构造标签或快照。
将反序交给弦图与完美消去序中的线性验证器，便得到O(n+m)的识别流程。通过后可构造最优着色及最大团证书；没有通过时，三点违例易于重算，若还要求直接展示一个诱导长圈，则应另计圈提取算法的成本。
终结任务要求交换边表输入次序后重跑：搜索排列允许改变，弦性、最优颜色数及全部极大团必须保持。这比只重放同一个并列顺序更能检验接口是否写对。