Caută componente conectate

Definiția componentelor conectate

Conceptul de componente conexe derivate din conceptul de conectivitate a graficului. Pur și simplu pune, o componentă conectată - o parte a graficului (subgraful) este conectat. Formal, componenta conectată a - un set de noduri, între orice pereche de care există o cale.

Contorizarea ilustrația are trei componente conectate, vopsite în culori diferite. Se poate remarca faptul că, chiar și un singur nod, izolat de restul graficului este o componentă conectată.

Conceptul general al conectivității se aplică numai grafice neorientate. Pentru o descriere a graficelor îndreptate sunt folosite conceptele de coerență puternică și slabă, dar ele sunt în afara limitelor materialului din acest capitol.

Cauta componente Algoritmul conectate

Pentru a găsi componentele conectate folosind DFS convenționale practic fără modificări (poate fi folosit BFS). Când porniți crawl din partea de sus a unuia, este garantat pentru a vizita toate nodurile la care este posibil pentru a obține, adică, toate componentei conectate, căruia îi aparține vârful inițial. Pentru a găsi toate componentele încearcă să ruleze runda de la fiecare nod la un moment dat, dacă nu am cruțat componenta sa anterioară.

punerea în aplicare

Dăm două exemple de realizare ale metodei cu diferite componente de stocare conectate.

Cea mai simplă opțiune: pur și simplu completați un $ $ matrice comp, în cazul în care $ comp [i] $ - numărul de componente conectate, la care face parte vârful $ i $.

În mod alternativ, stocate în mod explicit pentru fiecare componentă a vectorului nodurile care îi aparțin. Componente (vectori) stocate în vectorul (vectorilor).