fbpx

DFS – Parcugerea in adancime

0

Prin parcurgerea grafului G se întelege vizitarea, tuturor nodurilor, plecând de la un nod de plecare, vizitand in mod progresiv fiecare nod al grafului. Probabil ati auzit pana acum de DFS sau BFS

Un graf poate fi parcurs în următoarele două moduri:

Vom incepe sa prezentam parcurgerea in adancime (DFS).

Memorarea vecinilor

Inainte sa incep sa va descriu algoritmul, trebuie mai intai sa va prezint modul in care noi vom memora vecinii grafului. Probabil pana acum ati folosit liste de adiacenta, sau o matrice de adiacenta, pentru a tine minte vecinii oricarui nod din graf.

Vom folosii un vector dinamic, care ocupa memorie pe masura ce este folosit, nu va ocupa toata memoria atunci cand e declarat, cum se intampla in cazul vectorilor cunoscuti pana acum.

Pentru mai multe detalii despre acest, nou, tip de vector, puteti gasii: aici.

Deoarece in problema este vorba despre un graf neorientat, vom memora drumul de la nodul A la nodul B, cat si drumul de la nodul B la nodul A.

#include <vector>
const int NLIM = 100005;
vector < int > Edge[NLIM];

Includem bibleoteca vector, care contine functiile din primul link. Dupa care, definim cate noduri pot fi in total in problema, in cazul nostru, 100.000, dar o sa va obisnuiti treptat cu stilul meu de a declara mereu inca 5 pozitii in plus.

Dupa ce am introdus bibleoteca, declaram 100.000 de vectori: Edge[0], Edge[1], Edge[2], .. etc. In care vor fi retinute toate drumurile din nodul 0, 1, 2.. catre celalalte noduri. Mentionez inca o data: memoria totala ocupata de acest tip de vector este pana acum 0. Fata de 380 GB RAM, cat ar ocupa 100.005 de vectori cu 100.005 de elemente.

Edge[x].push_back(y);
Edge[y].push_back(x);

Trecem mai departe, iar aceste doua linii, de exemplu, memoreaza drumul de la nodul X, catre nodul Y, si drumul de la nodul Y catre nodul X (repet, fiind vorba despre un graf neorientat, trebuie retinute ambele drumuri).

Componente conexe

Sa incepem explicarea componentelor conexe prin realizarea unui desen care sa reprezinte nodurile si muchiile ce le avem date in problema.

Reprezentare graf problema dfs

Ce este o componenta conexa?

As vrea sa am caietul de informatica de la clasa pe la indemana, ca sa va dau definitia lunga si completa, dar in schimb va pot explica pe figura de mai sus. O componenta conexa se defineste ca fiind una dintre cele 3 culori din figura. Putem privii, altfel: „cate insule avem in total pe harta”. Avem 3 insule (culori): insula 1 (culoarea mov) – formata din nodurile 1, 2, 4; insula 2 (culoarea rosie) – formata din nodurile 3 si 5; insula 3 (culoarea neagra): formata din nodul 6.

Numarul de componente conexe (cerinta problemei) este dat de numarul de porniri ale algoritmului DFS. In problema vom pornii algoritmul DFS de 3 ori, deoarece avem 3 componente conexe.

Algoritmul DFS

Inainte de a incepe sa va explic algoritmul, vom adauga o ultima caracteristica nodurilor din graf. Daca nodul a fost accesat, acesta va fi marcat ca si „vizitat” si nu il vom mai vizita a doua oara. Pentru ca aceasta caracteristica nu poate avea decat doua valori 0 – fals, 1 – adevarat, vom declara variabila ca fiind una de tip bool.

bool beenThere[NLIM];

Am declarat cate cate o variabila bool pentru fiecare nod, prin intermediul unui vector! beenThere[i] – semnificand vizitarea nodului „i”.

void DFS(intNode)
{
    beenThere[Node] = true;
    for(unsigned int i = 0; i < Edge[Node].size(); i++)
    {
        int Next = Edge[Node][i];
        if(!beenThere[Next])
            DFS(Next);
    }
}
Primul pas in algoritmul DFS este sa marcam nodul ca fiind vizitat, dupa care sa parcurgem vecinii nodului curent, iar daca acestia nu au fost vizitati, vom pornii un alt algoritm DFS, si la final ne vom intoarce de unde am plecat, folosind proprietatea de recursivitate. Veti vedea mai multe detalii in animatia din tutorialul video.
La final, dupa ce am parcurs o componenta conexa (insula / culoare), vom verifica daca am parcurs toate nodurile, iar daca nu le-am parcurs, vom da drumul altui algoritm DFS, numarand in acelasi timp de cate ori am pornit un alt DFS.
for(int i = 1; i <= N; i++)
{
    if(!beenThere[i])
    {
        answer += 1;
        DFS(i);
    }
}
Tot algoritmul, pentru obtinerea celor 100 de puncte pentru aceasta problema poate fi gasit aici: pastebin.com
Comentarii
Se incarca comentariile...

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More