Лексикографска претрага у ширину

Из Википедије, слободне енциклопедије

У информатици, лексикографска претрага у ширину или Lex-BFS је линеарни алгоритам за обилазак чворова графа, који се користи као део других алгоритама за рад са графовима као што је алгоритам за оптимално бојење графа или удаљеност чворова у графу. Алгоритам за конструисање лексикографске претраге у ширину обилази чворове графа у другачијем поретку у односу на обичну претрагу у ширину сваки Lex-BFS обилазак је могући BFS обилазак али не и обрнуто. Лексикографска претрага у ширину је алгоритам за обилазак графа базиран на идеји партиционисања.

Алгоритам[уреди]

Алгоритам за лексикографску претрагу у ширину у ствари замењује поредак чворова из стандардне претраге у ширину са лексикографски уређеним поретком чворова. За имплементацију овог алгоритма, као и код обичне претраге у ширину користимо структуру ред. У сваком кораку се један чвор испише, затим се у ред додају сви његови непосећени суседи, и онда се тај чвор уклони из реда. Ово се ради све док ред не постане празан. Кад ред постане празан то значи да смо обишли све чворове из графа. Псеудо код:

   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 Σ.

Сваки чвор је обрађен само једном, свака грана је обрађена само уколико су обрађена оба чвора која је ограничавају, и (са одговарајућом поставком елемената у Σ омогућава се премештање чворова у константном времену) свака итерација унутрашње петље траје константно време. Стога, слично као једноставнији алгоритми за претрагу графова(претрага у ширину (BFS) или претрага у дубину (DFS)), овај алгоритам је линеарне сложености.

Алгоритам се зове лексикографска претрага у ширину због лексикографског поретка који добијамо као резултат ове претраге.

Бојење графа[уреди]

Лексикографска претрага претрага у ширину може да се користи код проблема бојења графа, тј. ако су чворови смештени у низ у лексикографском поретку (коришћењем алгоритма за лексикографски обилазак у ширину) онда похлепни алгоритам за бојење графова може обојити тај граф у линеарном времену, а поред тога загарантвоано је оптимално бојење графа.[1]


Белешке[уреди]

  1. ^ Brandstädt, Le & Spinrad (1999), Theorem 5.2.4, pp. 71.

Референце[уреди]