การค้นหาในแนวกว้างตามการเรียงลำดับแบบพจนานุกรม

Lexicographic Breadth-First Search เป็นวิธีการค้นหาข้อมูลแบบหนึ่งที่คล้ายกับ breadth-first search แต่เปลี่ยนจากการนำเส้นเข้าแถว เปลี่ยนเป็นนำ set ของจุดเข้าแถวแทน โดยที่ set ในแถวนั้นคือ set ที่เกิดจากการแบ่งกลุ่มจุด ที่ยังไม่ได้รวมเข้าด้วยกัน ในแต่ละขั้นตอน จะทำการดึง จุด v (จุดใดๆ ใน set)จาก set หน้าสุดของแถว ออกมาจากแถวและ ถ้าการดึงนั้นทำให้ทำให้ set นั้นว่างก็จะดึง set นั้นออกจากแถว หลังจากนั้น ทุกๆ set ในแถวจะถูกแทนที่ด้วย 2 subsets คือ set ที่มี v เชื่อม และ set ที่ไม่มี v เชื่อม โดย set ที่มี v เชื่อมจะถูกนำมาเข้าแถวก่อน อีกแบบหนึ่ง วิธีการทำงานดังนี้ :

- เริ่มใส่ทุก set เข้าไปใน แถว โดยแต่ละset จะมี จุด 1 จุด

- ให้แถวผลลัพธ์เป็นว่างเปล่า

- ถ้ายังมีset ในแถว :

    - หาจุด v และ เอาจุด v ออกจาก set แรกในแถว

    - ถ้า set แรกในแถวว่างแล้ว ให้เอา set นั้นออกจากแถว

    - ใส่ v ลงไปแถวผลลัพธ์

    - ในทุกๆ จุด w ที่จุดvเชื่อมได้ ซึ่งอยู่ใน set ในแถว :

         - ถ้า set นั้นๆ ยังไม่ได้ แทน w ด้วย v ให้สร้าง set ใหม่ แล้ว ใส่ set ใหม่ไว้หน้า set นั้นๆ ถ้าไม่ ให้ set ใหม่ไว้ด้านหนัง set นั้นๆ

         - ย้าย w  ไปที่ set ใหม่ แล้วถ้า set ที่ถูกดึง w ออกนั้นว่างก็ให้ดึง set นั้นออกจากแถว

แต่ละจุด จะถูกทำงานครั้งเดียว แต่ละเส้นจะถูกใช้งานเมื่อ จุด 2 จุด ถูกนำมาคำนวณ และ ถ้าการย้าย set ในแถวคอยมีความเร็วแบบคงที่ การวนซ้ำแต่ละครั้งจะมีการวนซ้ำแบบคงที่เช่นกัน จึงเหมือนกับการใช้ Breadth-First Search กระบวนการนี้ใช้เวลาแบบคงที่

การที่เรียกว่า Lexicographic Breadth-First Search เพราะว่ากระบวนการนี้ได้สร้างการจัดเรียงที่สามารถนำไปใช้ในการเรียกคำศัพท์ทางพจนานุกรมได้

(เพิ่มเติม) Lexicographic breath-first-search ordering(Lex-BFS) เป็นการจัดเรียง จุด ของกราฟ โดยผ่านกระบวนการต่อไปนี้ 1. ทำเครื่องหมาย จุดไหนก็ได้บนกราฟให้เป็น 1 แล้วตั้งว่า ได้ผ่านกราฟไปแล้ว 2. ถ้ายังมีจุดที่ไม่ได้ผ่าน ให้เลือกจุดที่ยังไม่ได้ผ่านนั้นซึ่งต้องเป็นจุดที่ติดกับจุดที่ผ่านไปแล้วที่เล็กที่สุด(สุดแรก)โดยวิธีการ Lexicographic breath-first-search ordering ตั้งให้เป็นจุดที่ผ่านไปแล้ว และใส่ไว้ในลำดับต่อไป

ซึ่งการเปรียบเทียบ 2 ลิส นั้น สามารถเปรียบเทียบได้ดังนี้ จัด list ทั้ง 2 อันแบบลำดับเพิ่ม หาจุดที่เล็กที่สุดที่ทั้ง 2 ลิสต่างกัน ซึ่งจุดที่มีเลข น้อยกว่าจะถือว่าเล็กกว่า( อยู่ก่อน ) ทำให้ลิสนั้นอยุ่ก่อนด้วย

ทฤษฎี 1 กราฟใดๆ เป็น chordal graph ก็ต่อเมื่ออินเวิสของการจัดเรียงแบบ Lex-BFS ของกราฟนั้น เป็นการจัดเรียงแบบ perfect elimination ordering

ถ้าอินเวิส ของ Lex-BFS เป็น perfect elimination ordering แล้วกราฟนั้นเป็น chordal graph ถ้ากราฟ G เป็น chordal graph และ อินเวิสของ Lex-BFS ของ G ไม่เป็น perfect elimination ordering แล้วแสดงว่าจะต้องมี จุด ที่ n0 > n1 > n2 ซึ่ง n0 ติดกับ n1 n2 แต่ n1 ไม่ติดกับ n2 เราสามารถเขียน ลำดับของจุดโดยการเรียงแบบมากไปน้อย ว่า n0 > n1 > n2 > …. > nL-1 ผิดถ้า l >= 3 และกราฟย่อย ( L=3; n3-1 =>n2 => n2>n2 ผิด ) เราใช้ Lex-BFS ในลำดับอื่นๆแบบที่แสดงไปก่อนหน้านี้ แต่ยกเว้นว่าลำดับที่ ได้อยู่ในการจัดเรียงจากน้อยไปมากอยู่แล้ว ถ้าอินเวิสของการจัดเรียงแบบ Lex-BFS ไม่เป็น perfect elimination ordering แล้วแสดงว่าจุดที่มีลำดับไม่ดี จากการจำนวนลำดับนั้นจำกัด จะต้องมีลำดับที่ไม่ดีอยู่ซึ่ง n0 > n1 > n2 … > nL-1 ซึ่งจะถือว่ามาก่อนในการจัดเรียงแบบ Lex-BFS ซึ่งเราจะแสดงว่ามันขัดแย้งกัน พิจารณาในขณะที่ จุดnL-2 ถูกผ่านนไปแล้วใน Lex-BFS แล้วครั้งนี้ จุด nL-3 ยังไม่ได้ถูกผ่าน และมันติดกับจุดnL-1 ซึ่งถูกตั้งให้ผ่านแล้ว และไม่ได้ติดกับจุด nL-2 เพราะว่าจุด nL-2 ถูกเลือกให้เป็นจุดต่อไปในการเข้าถึง มันจะต้องมีจุด nL < nL-1 ที่ติดกับ nL-2 แต่ไม่ติดกับ nL-3 เราอ้างว่า nL ไม่สามารถติดกับ จุด ใดๆ โดยที่จุด nI โดย 0<= I < L-2 ถ้า nL ติดกับ จุด nL-3-2I เมื่อ I >=1 ; ให้ I เป็นตัวเลขที่น้อยที่สุดนั้น แล้วจะได้ nL-3-2I, nL-1-2I จะได้ nL เป็น Lex-BFS ที่มาก่อนซึ่งเป็นลำดับที่ผิด ซึ่งขัดแย้งกัน ถ้า nL ติดกับ nL-1 เราจะได้ กราฟที่ไม่มี chord ที่เป็น cycle ซึ่งยาวอย่างน้อย 4 ซึ่งขัดแย้งกับสมมุติฐานที่เราให้มันเป็น chordal graph แม้ว่า nL จะติดกับ nL-2 เท่านั้น ด้วยเหตุนี้ n0 > n1 > n2 …. > nL-2 > nL-1 > nL เป็นตัวเล็กที่สุด ตามการจัดเรียง Lex-BFS ซึ่งเป็นลำดับที่ผิด ซึ่งขัดแย้งกัน จึงการที่ไม่มีลำดับที่ผิดของ อินเวิสของการจัดเรียงแบบ Lex-BFS เป็น perfect elimination ordering