h2. Indicaţii de rezolvare
O prima idee ar fi generarea tuturor submultimilor de $N-1$ muchii, verificarea daca muchiile selectate formeaza un arbore si retinerea solutiei optime. Aceasta rezolvare este cea mai evidenta si are complexitatea $O(2^N^*N)$ si obtine aproximativ $20$ de puncte.
O prima idee ar fi generarea tuturor submultimilor de $N-1$ muchii, verificarea daca muchiile selectate formeaza un arbore si retinerea solutiei optime. Aceasta rezolvare este cea mai evidenta dar are complexitate exponentiala si obtine aproximativ $20$ de puncte.
Presupunand ca sunt deja alese $N-2$ muchii care nu formeaza cicluri, in alte cuvinte formeaza $2$ arbori, trebuie sa se mai aleaga inca o muchie, si anume muchia minima care garanteaza conectivitatea arborilor. De la aceasta idee deducem ca cel mai bine ar fi sa adaugam muchii de cost minim, cat timp aceste muchii nu creaza cicluri.
Daca se sorteaza muchiile si se parcurg in ordinea sortarii, este mereu util sa adaugam la solutie muchia de cost minim cat timp aceasta nu creaza un cicluri. Aceasta solutie are complexitate $O(N*M + Mlog{~2~}M)$, deoarece iterarea prin cele $M$ muchii are complexitate {$O(M)$}, iar parcurgerea dfs pentru verificarea ciclurilor este {$O(N)$}. O astfel de solutie se poate vedea 'aici':job_detail/229653?action=view-source si ar trebui sa ia $40-50$ de puncte, in functie de implementare.
Parcurgerea dfs este redundanta, deoarece verificarea daca $2$ noduri, cele pe care le leaga muchia, sunt in aceeasi grupa se poate face in $O(log{~2~}N)$ cu 'multimi disjuncte':/problema/disjoint. Astfel complexitatea se reduce la $O(M*log{~2~}N + M*log{~2~}M)$ pentru ca se alege fiecare muchie si pentru fiecare muchie se verifica in $O(log{~2~}N)$ utilitatea ei.Pentru o optimizare mai departe se pot apela diferite metode de sortare care se bazeaza pe inexactitatea reprezintarii numerelor in calculator. De obicei nu trebuie optimizata sortarea. O reprezentare grafica se poate gasi "aici":http://en.wikipedia.org/wiki/Kruskal%27s_algorithm. Acest algoritm se numeste Kruskal si implementarea sa se poate vedea 'aici':job_detail/229317?action=view-source.
Daca se sorteaza muchiile crescator dupa costul asociat si se parcurg in ordinea sortarii, este mereu util sa adaugam la solutie muchia de cost minim cat timp aceasta nu creaza un ciclu, sau altfel spus, nodurile pe care le uneste nu sunt deja in aceeasi componenta conexa. Aceasta solutie are complexitate $O(N*M + Mlog{~2~}M)$, deoarece iterarea prin cele $M$ muchii are complexitate {$O(M)$}, iar 'parcurgerea dfs':problema/dfs pentru verificarea ciclurilor se realizeaza in timp {$O(N)$} la fiecare pas. O astfel de solutie obtine 40-50 de puncte, in functie de implementare, si se poate vedea 'aici':job_detail/229653?action=view-source.
Pentru a optimiza solutia de mai sus este suficient la fiecare pas sa verificam daca cele doua noduri pe care le uneste muchia curenta sunt in aceeasi componenta conexa, operatie care se poate realiza in timp {$O(1)$} amortizat, cu ajutorul 'multimilor disjuncte':problema/disjoint. Astfel complexitatea se reduce la $O(M + M*log{~2~}M)$. O reprezentare grafica se poate gasi "aici":http://en.wikipedia.org/wiki/Kruskal%27s_algorithm. Acest algoritm se numeste Kruskal si implementarea sa se poate vedea 'aici':job_detail/229317?action=view-source.
Pentru a intelege o alta solutie se presupune urmatorul scenariu: Existand deja calculat un subarbore minim vrem sa introducem in el inca un nod. Evident vom introduce nodul care are muchia minima care il leaga de subarborele deja format. Aceasta solutie are complexitate $O(N*M)$, deoarece incepem cu un nod aleator si iterand tot adaugam inca cate un nod, pana sunt toate adaugate. Pentru a vedea nodul cu muchie minima parcurgem cele M muchii. Acest algoritm se poate optimiza, daca pentru fiecare nod se tine muchia minima curenta care il leaga de subarborele existent. La fiecare introducere a unui nod in subarbore, se actualizeaza toti vecinii lui.Aceasta solutie are complexitate $O(N^2^)$ si ar trebui sa obitna $50$ puncte.
Pentru a se optimiza mai departe algoritmul pentru extragerea minimului se foloseste un "heap":http://en.wikipedia.org/wiki/Heap_(data_structure) , iar de fiecare data cand se introduce un nod in subarbore sunt parcurse muchiile lui si actualizate nodurile. Astfel complexitatea devine $O(M*log{~2~}N)$, o optimizare semnificativa fata de Kruskal, acest algoritm se numeste "Prim":http://en.wikipedia.org/wiki/Prim%27s_algorithm. O sursa implementata se poate vedea "aici":job_detail/229651?action=view-source.
