Exemple de utilizare a seturilor divizate
Exemplul 1. Luați în considerare problema izolării componentelor conectate ale unui grafic nedirecționat. Să ne amintim că componenta conectată este maximul pentru care încorporează un subset de noduri ale grafului astfel încât oricare două noduri conectate printr-un lanț. Noi credem că vârful numerotate și fiecare margine reprezentat printr-o pereche () un număr de noduri. De asemenea, presupunem că setul de margini nu este gol.
Algoritm pentru separarea componentelor conectate ale unui grafic nedirecționat
Evident, subseturile construite ale colecției vor reprezenta componentele de conectivitate necesare. Folosirea numelor operațiilor de bază ale colecției de seturi separate. algoritmul prezentat mai sus poate fi scris în următoarea formă:
Exemplul 2. Luați în considerare un grafic conectat nedirecționat fără bucle ale căror margini sunt atribuite numere reale pozitive ca ponderi. Este necesar să se construiască un copac spanning. acoperind toate vârfurile graficului și având greutatea totală minimă a marginilor care intră în el. Deci, lăsați graficul dat a mai multe vârfuri sunt numerotate, și o multitudine de nervuri. Fiecare margine a setului este asociată cu o pereche de vârfuri de capăt și un număr - greutatea sa. Pentru a rezolva această problemă au fost propuse diferite algoritmi. Vom analiza algoritmul. care a proiectat Kruskal.
Rețineți că în timpul funcționării algoritmului setul va conține marginile care formează subgraful aciclic al graficului original, care este o pădure constând dintr-un anumit număr de arbori. Absența ciclurilor este garantată prin verificarea "Dacă" în clauza 6 a algoritmului descris. De fapt, atunci când două subtreri se îmbină într-un copac folosind marginea găsită în pasul 3.
Dacă graficul inițial este conectat, așa cum se menționează în declarația problemei, atunci setul construit cu ajutorul unui astfel de algoritm va reprezenta în mod evident un copac. acoperind toate vârfurile graficului original. Dovada că greutatea totală a coastelor care intră în ea va fi minimă, poate fi găsită în secțiunea "Grafice".
Algoritmul utilizează în mod natural structura seturilor separate. Să acordăm atenție operației de căutare din setul de margini cu greutatea minimă. Eficiența acestei operațiuni depinde în mare măsură de alegerea structurii de date pentru stocarea setului. Tehnicile pentru executarea eficientă a acestei operațiuni sunt discutate în secțiunea "Cozi de prioritate".
Reprezentarea seturilor separate cu o matrice
Fie un set de elemente din care se va construi o colecție de subseturi separate. Una dintre modalitățile evidente de a reprezenta o colecție este reprezentarea ei cu o matrice. În acest fel, pentru fiecare element din celula corespunzătoare a matricei, punem numele (elementul canonic) al subsetului la care aparține elementul. Dacă elementul nu aparține niciuneia dintre subseturile colecției, atunci în celula-a scrie 0.
Operațiuni de implementare utilizând o matrice
Indicați printr-o serie de lungimi, prin care vom reprezenta colecția. O colecție goală este reprezentată de o matrice completă cu zerouri.
Operația CREATE () se realizează prin scrierea elementului în celulă cu numărul. Timpul operației.
Operația UNIFY () este efectuată după cum urmează. Elementele matricei sunt privite, iar în celulele în care a fost scris numele, este introdus un nume nou. În consecință, numele subsetului nou format va fi și va înceta să fie numele oricărui subset. Evident, timpul acestei operațiuni este.
Operația FIND () produce ca conținut al elementului cu numărul din matrice. Timpul operației.
Cu o astfel de realizare a seturilor separate. Este evident că timpul de executare a operațiunilor arbitrare, printre care operațiunile UNIFY, este o valoare.
Articole similare
Trimiteți-le prietenilor: