Conexitate

Parcurgerea în lățime a grafurilor are două proprietăți foarte valoroase: prima - permite determinarea tuturor nodurilor accesibile din unul dat (componenta sa conexă); a doua - permite determinarea unui drum minim (ca număr de muchii) între nodul de start și toate cele în care se poate ajunge din el.