De ce o singură parcurgere nu vizitează tot graful
Identifică nodurile inaccesibile din componenta de pornire și pornește parcurgeri suplimentare fără să resetezi greșit marcajele globale.
În acest material
Într-un graf neorientat, o componentă conexă este un grup maximal de noduri între care există drumuri. O parcurgere pornită dintr-un nod ajunge numai la nodurile componentei sale. Nu poate traversa o muchie care nu există pentru a ajunge în alt grup.
Un exemplu cu trei componente
Consideră cinci noduri și numai muchiile 1-2 și 3-4. Componentele sunt {1,2}, {3,4} și {5}. Nodul 5, deși nu are vecini, formează singur o componentă. O parcurgere pornită din 1 vizitează numai 1 și 2.
BFS este parcurgerea în lățime, care folosește o coadă. DFS este parcurgerea în adâncime, care continuă pe o ramură înainte de revenire. Ambele rămân în componenta sursei dacă graful este neorientat.
Bucla exterioară găsește grupurile rămase
Pentru a vizita întregul graf, treci prin toate nodurile. Când găsești un nod nevizitat, pornești din el o parcurgere și numeri o componentă nouă. Parcurgerea marchează toate nodurile acelui grup.
Marcajele trebuie păstrate între aceste porniri. Dacă le ștergi după fiecare componentă, poți număra din nou grupuri deja procesate. Resetarea este potrivită între cazuri de test independente, nu între componentele aceluiași graf.
Cu nodurile 1..5 și muchiile 1-2,3-4, componentele sunt {1,2}, {3,4}, {5}. Nodul izolat 5 formează și el o componentă.Mărește schema ↗
Nodurile izolate nu trebuie omise
Dacă construiești lista nodurilor numai din capetele muchiilor citite, riști să pierzi nodurile fără vecini. Numărul total de noduri din enunț definește domeniul parcurgerii exterioare. O listă de vecini goală nu înseamnă că nodul nu există.
Testează un graf fără nicio muchie: pentru n noduri, are n componente. Testează apoi un graf conex, unde o singură pornire este suficientă. Aceste extreme verifică atât bucla exterioară, cât și păstrarea marcajelor.
Atenție la grafurile orientate
Dacă muchiile au sens, accesibilitatea nu mai este simetrică. Faptul că poți ajunge din A în B nu garantează că poți reveni din B în A. Componentele tare conexe și cele slab conexe sunt concepte diferite și cer definiții și algoritmi potriviți.
Prin urmare, metoda simplă de numărare descrisă aici are ca premisă graful neorientat. Nu schimba doar modul de citire a muchiilor și presupune că numărul pornirilor are aceeași semnificație.
Continuă cu parcurgerile, conexitatea și reprezentarea grafurilor.
Întrebări frecvente
Ce este o componentă conexă?
Un grup maximal de vârfuri ale unui graf neorientat între care există drumuri. O parcurgere pornită dintr-un vârf vizitează exact componenta accesibilă din el.
Cum număr toate componentele unui graf neconex?
Parcurge lista vârfurilor. Pentru fiecare vârf încă nevizitat, mărește contorul și pornește o parcurgere care marchează întreaga componentă. Nu reseta marcajele între porniri.
Un vârf izolat este o componentă conexă?
Da. Formează singur o componentă, chiar dacă nu are nicio muchie. O soluție care pornește numai din capetele muchiilor poate omite astfel de vârfuri.