Parcurgerea grafurilor neorientate

Prin parcurgerea unui graf neorientat se înţelege examinarea în mod sistematic a vârfurilor, plecând dintr-un vârf dat start, astfel încât fiecare vârf accesibil din start pe muchii incidente două câte două să fie vizitat o singură dată. Trecerea de la un vârf x la altul se face prin examinarea, într-o anumită ordine a vecinilor săi.

Parcurgerile grafurilor sunt frecvent utilizate în rezolvarea multor probleme. Animația de mai jos, prezintă modul în care se parcurge un labirint folosind mecanisul parcurgerii în adâncime.

Citește mai departe: 

Parcurgerea în adâncime

Parcurgerea în adâncime reprezintă explorarea "naturală" a unui graf neorientat. Este foarte asemănătoare cu modul în care un turist vizitează un oraș în care sunt obiective turistice (vârfurile grafului) și căi de acces între obiective (muchiile). Vizitarea orașului va avea loc din aproape în aproape: se pleacă de la un obiectiv de pornire, se continuă cu un obiectiv învecinat cu acesta, apoi unul învecinat cu al doilea, etc. ...

Parcurgerea în lățime

Se parcurge vârful de start, apoi vecinii acestuia, apoi vecinii nevizitați ai acestora, etc, până când sunt vizitate toate vârfurile accesibile. Practic, pentru a stabili ordinea de vizitare se folosește o coadă, iar pentru a stabili dacă un vârf a fost sau nu vizitat se foloseşte un vector caracteristic. ...

Aplicații ale parcurgerii grafurilor

Parcurgerea grafurilor neorientate poate fi folosită în rezolvarea unei game largi de probleme: verificarea conexității unui graf, determinarea componentelor conexe ale unui graf, determinarea unor lanțuri în graf, verificarea faptului că un graf este bipartit, etc. ...