Leksikografska pretraga u širinu

U informatici, leksikografska pretraga u širinu ili Lex-BFS je linearni algoritam za obilazak čvorova grafa, koji se koristi kao deo drugih algoritama za rad sa grafovima kao što je algoritam za optimalno bojenje grafa ili udaljenost čvorova u grafu. Algoritam za konstruisanje leksikografske pretrage u širinu obilazi čvorove grafa u drugačijem poretku u odnosu na običnu pretragu u širinu svaki Lex-BFS obilazak je mogući BFS obilazak ali ne i obrnuto. Leksikografska pretraga u širinu je algoritam za obilazak grafa baziran na ideji particionisanja.

Algoritam

Algoritam za leksikografsku pretragu u širinu u stvari zamenjuje poredak čvorova iz standardne pretrage u širinu sa leksikografski uređenim poretkom čvorova. Za implementaciju ovog algoritma, kao i kod obične pretrage u širinu koristimo strukturu red. U svakom koraku se jedan čvor ispiše, zatim se u red dodaju svi njegovi neposećeni susedi, i onda se taj čvor ukloni iz reda. Ovo se radi sve dok red ne postane prazan. Kad red postane prazan to znači da smo obišli sve čvorove iz grafa. Pseudo kod:

   Initialize a sequence Σ of sets, to contain a single set containing all vertices.
   Initialize the output sequence of vertices to be empty.
   While Σ is non-empty:
       Find and remove a vertex v from the first set in Σ
       If the first set in Σ is now empty, remove it from Σ
       Add v to the end of the output sequence.
       For each edge v-w such that w still belongs to a set S in Σ:
           If the set S containing w has not yet been replaced while processing v, create a new empty replacement set T and place it prior
           to S in the sequence; otherwise, let T be the set prior to S.
           Move w from S to T, and if this causes S to become empty remove S from Σ.

Svaki čvor je obrađen samo jednom, svaka grana je obrađena samo ukoliko su obrađena oba čvora koja je ograničavaju, i (sa odgovarajućom postavkom elemenata u Σ omogućava se premeštanje čvorova u konstantnom vremenu) svaka iteracija unutrašnje petlje traje konstantno vreme. Stoga, slično kao jednostavniji algoritmi za pretragu grafova(pretraga u širinu (BFS) ili pretraga u dubinu (DFS)), ovaj algoritam je linearne složenosti.

Algoritam se zove leksikografska pretraga u širinu zbog leksikografskog poretka koji dobijamo kao rezultat ove pretrage.

Bojenje grafa

Leksikografska pretraga pretraga u širinu može da se koristi kod problema bojenja grafa, tj. ako su čvorovi smešteni u niz u leksikografskom poretku (korišćenjem algoritma za leksikografski obilazak u širinu) onda pohlepni algoritam za bojenje grafova može obojiti taj graf u linearnom vremenu, a pored toga zagarantvoano je optimalno bojenje grafa.

Reference

• Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy (1999), Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, ISBN 978-0-89871-432-6 .
• Bretscher, Anna; Corneil, Derek; Habib, Michel; Paul, Christophe (2008), „A simple linear time LexBFS cograph recognition algorithm”, SIAM Journal on Discrete Mathematics, 22 (4): 1277—1296, doi:10.1137/060664690 .
• Corneil, Derek G. (2004), „Lexicographic breadth first search – a survey”, Graph-Theoretic Methods in Computer Science, Lecture Notes in Computer Science, 3353, Springer-Verlag, str. 1—19 .
• Habib, Michel; McConnell, Ross; Paul, Christophe; Viennot, Laurent (2000), „Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing” (PDF), Theoretical Computer Science, 234 (1–2): 59—84, doi:10.1016/S0304-3975(97)00241-7, Arhivirano iz originala (PDF) 26. 7. 2011. g., Pristupljeno 26. 5. 2013 .
• Rose, D. J.; Tarjan, R. E.; Lueker, G. S. (1976), „Algorithmic aspects of vertex elimination on graphs”, SIAM Journal on Computing, 5 (2): 266—283, doi:10.1137/0205021 .