DFS – Parcugerea in adancime

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:

• în adâncime (DFS = Depth First Search)
• în lătime (BFS = Breadth First Search)

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.

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);
    }
}

for(int i = 1; i <= N; i++)
{
    if(!beenThere[i])
    {
        answer += 1;
        DFS(i);
    }
}