Conectați-vă pentru a adăuga un comentariu.
Transcrierea Determinarea componentelor conectate în grafic
Definiția. Dacă graficul nu este conectat, este numit deconectat.
grafic neconectat este format din componente conectate.
componentă conectată
- set de vârfuri astfel încât fiecare nod al acestui set este calea către un alt vârf al acestui set, dar nici unul dintre care partea de sus a acestui set nu se poate obține într-un vârf în afara acestui set. Este evident că suma numărul de noduri ale componentelor conectate este egal cu numărul de noduri.
Rețineți că componenta conectată poate consta dintr-un singur nod. În cazul în care numărul n vârfuri, el poate consta din mai mult de n componente conectate. Într-o componentă conectată grafic conectat numai.
punerea în aplicare
algoritmul
Conceptul grafic
Cum pentru a determina dacă un grafic conectat? Și cum pentru a determina numărul de componente conectate?
Exemplu: este conectat în figura de mai jos graficul. Cu toate acestea, să spunem, dacă ștergeți o muchie între nodurile 4 și 5, atunci nu va fi conectat - din top 5 nu va fi capabil de a ajunge la orice alt nod.
conectat ferm orgaf
Definiția. Un grafic este conectat dacă pentru oricare două vârfuri v, w există o cale de la v la w
Dacă graficul este conectat și fără cicluri (de exemplu, un pom), îndepărtarea oricărei margine va duce la o pierdere de conectivitate.
Definiția. Digraph este numit unul unilateral conectat puternic dacă pentru oricare două vârfuri, cel puțin un accesibil de altul.
Figura prezintă graficul cu două componente conectate.
In orice grafic neconectat component conectat nu este mai mare n-1 noduri. Dacă știți că Contele k componente conectate, atunci da apreciere și mai riguroasă: orice componentă conectată este format din cel mult n-k + 1 noduri.
Dacă graficul deconectat k componente conectate, pentru a obține un grafic conectat pentru a adăuga la graficul de cel puțin k-1 muchie.
Alegeți un nod A și marcați-o ca vizitate (1), respectiv, restul nu se sprijine încă vizitate (0):
Determinarea componentelor graficului
Un cred nodul curent. Apoi vom proceda după cum urmează. Marcarea vârfurilor adiacente nevizitate: pentru partea de sus curent în căutarea adiacente acesteia, nu a fost încă nevizitate, și să le marcați ca vizitate.
Să presupunem că ne-am întors k noduri novopomechennyh (arătat chiar deasupra lor 3). La rândul său alege una dintre ele curente și noduri nevizitate recursiv executa marcate adiacente acesteia. Pentru nodul curent nu funcționează recursivitate, în cazul în care acest vârf nu este vârfuri adiacente, care nu sunt încă marcate ca fiind vizitate.
Dacă după aceste acțiuni toate nodurile vor fi marcate ca vizitate, graficul este conectat sau deconectat.
Concluzie: nu toate din partea de sus a vizitat Earl a apărut incoerent.
Pentru a pune în aplicare un pic mai convenabil pentru a ocoli în profunzime:
int n;
vector
bool utilizate [MAXN];
vector
void DFS (int v) utilizat [v] = true;
comp.push_back (v);
pentru (size_t i = 0; i
DFS (a);
>
>
find_comps void () pentru (int i = 0; i
pentru (int i = 0; i
DFS (i);
cout <<"Component:";
pentru (size_t j = 0; j
>
Algoritmul pentru identificarea
cantitate
component conectat.
Pentru a rezolva, puteți utiliza ca un by-pass în profunzime și by-pass lat.
De fapt, vom putea produce o serie de runde: prima rundă de la lansarea primului Vertex toate nodurile care, în acest sens el a umblat - formează primul component conectat. Apoi vom găsi primul dintre nodurile rămase care nu au fost încă vizitate, și a alerga eludare a acesteia, găsindu-al doilea component conectat. Și așa mai departe, până când toate nodurile devin marcate.
Nadzhafova Lala TK-31