Бипартитивни граф — разлика између измена

 

Алтернативно овоме, слична процедура може да се примени са методом [[претрага у ширину]] уместо претраге у дубину. Опет, сваки чвор добија супротну боју од свог родитеља у стаблу претраге. Ако, када је неки чвор обојен, онда постоји и грана која га спаја са претходно обојеним чвором том бојом. Онда је та грана заједно са путањом у стаблу која настаје при примени алгоритма претраге у дубину која спаја та два краја са њиховим најнижим заједничким претком чини циклус непарне дужине. Ако се алгоритам заврши без да је пронашао циклус непарне дужине на овај начин, онда је сигурно нашао исправно бојење, и сигурно може да се закључи да је овај граф бипартитиван.

 

За графове са убацивањем n-те дужи или неког другог облика у Еуклидовој равни, могуће је да се тестира да ли је граф бипартитиван и вратити или две боје или циклус непарне дужине у<math>O(n\log n)</math>, времену, иако граф сам по себи има до <math>\Omega(n^2)</math> грана.