Structuri de Date 2023 - C12: Grafuri 3

Structuri de Date

Curs 12: Grafuri 3

Cuprins:

Algoritmul lui Kosaraju pentru găsirea componentelor tare conexe (graf orientat)
Reprezentări pentru grafuri ponderate
Algoritmul lui Dijkstra pentru găsirea celor mai scurte drumuri

1. Găsirea componentelor tare conexe (graf orientat)

Graf orientat:

Componentele tare conexe:

DFS(1) DFS(2) DFS(3) DFS(7) DFS(8) DFS(4) DFS(6) DFS(5)
DFS(9) DFS(13) DFS(14) DFS(10) DFS(15) DFS(11) DFS(12) DFS(16)

Ordinea finala:4 8 7 3 5 6 2 110 16 12 11 15 14 13 9

Lansam DFS din fiecare nod nevizitat in ordine.
La intoarcere din DFS printam nodul.
Observam ca DFS(1) parcurge componente rosii si verzi.DFS(9) parcurge albastru, galben (si verzi daca n-ar fi deja vizitate).
Exista vreo ordine de aplicare DFS astfel incat sa parcurga numai fiecare componenta tare conexa???
Da, de exemplu 4 12 1 9 vor colora doar componentele verde, galben, rosu, albastru. De ce este asa?

Graf transpus:

Algoritmul lui Kosaraju:

- initializăm toate nodurile ca fiind nevizitate
Lansăm parcurgrea în adâncime (DFS) din primul nod nevizitat.
La întoarcerea din recursie (exact ca la SDR postordine, la arbori) punem nodul într-o listă (array).
- Continuăm cu următorul nod nevizitat până la epuizarea lor.
Producem graful transpus prin inversarea direcției muchiilor.
- initializăm toate nodurile ca fiind nevizitate
Începând cu ultimul nod din listă nevizitat lansăm din nou DFS. Acest DFS va colora o singură componentă tare conexă.
- Continuăm cu următorul nod nevizitat până la epuizarea lor.

Corectitudinea este bazată pe următoarele proprietăți:

Componentele tare conexe sunt invariante la transpunerea grafului
Graful componentelor tare conexe este un graf orientat aciclic (directed acyclic graph, DAG)
Pentru a parcurge izolat o componentă conexă, lansăm o parcurgere dintr-o componentă cu grad extern 0, care devine vizitată, o considerăm eliminată din graf, iar apoi continuăm cu restul grafului.
Prima trecere DFS din algoritmul lui Kosaraju produce o ordonare specială a nodurilor cu proprietatea că există un nod roșu care apare după oricare nod verde (fig.2). Dacă este așa, după ce transpunem și rulăm DFS pe ordinea inversă: componenta roșie va fi colorată și vizitată înaintea celei verzi, izolând corect componenta roșie.

void tare_conexe(){    int* vizitat = new int[nod_maxim+1];    int* stiva = new int[nod_maxim+1];    int varf=0;    for (int i=1;i<=nod_maxim;i++)        vizitat[i]=0;
    for (int i=1;i<=nod_maxim;i++)        if (vizitat[i]==0)            tare_conexe_build_stiva(vizitat, i, stiva,varf);
    graf transpus;    for (int i=0; i<=nod_maxim;i++)        for (nod_lista* pointer = adiacenta[i].primul_element; pointer !=NULL;pointer = pointer->next)            transpus.adauga_muchie(pointer->info,i);
    for (int i=1;i<=nod_maxim;i++)        vizitat[i]=0;    int culoare=1;    for (int i=varf-1;i>=0;i--)        if (vizitat[stiva[i]]==0){            transpus.recursie_conexe(vizitat, stiva[i], culoare);            cout<<endl;        }
    cout<<endl;}
void tare_conexe_build_stiva(int* vizitat, int nod_curent, int* stiva, int &varf ){    vizitat[nod_curent]=1;    for (nod_lista* pointer = adiacenta[nod_curent].primul_element; pointer !=NULL;pointer = pointer->next)        if (vizitat[pointer->info]==0)            tare_conexe_build_stiva(vizitat,pointer->info,stiva,varf);
    stiva[varf++]=nod_curent;}
void recursie_conexe(int* vizitat, int nod_curent, int culoare){    cout<<nod_curent<<" ";    vizitat[nod_curent]=culoare;    for (nod_lista* pointer = adiacenta[nod_curent].primul_element; pointer !=NULL;pointer = pointer->next)        if (vizitat[pointer->info]==0)            recursie_conexe(vizitat,pointer->info,culoare);}

Output:
9 10 14 1315 16 12 111 5 6 23 4 8 7

2. Reprezentări pentru grafuri ponderate

Deseori este nevoie să reținem informații în muchii.

Uzual informația este o distanță sau cost necesar pentru a parcurge acea muchie.

Astfel de grafuri se numesc grafuri ponderate (weighted graph).

3. Algoritmul lui Dijkstra

Este un algoritm care calculează drumurile minime de la un nod al unui graf la toate celelalte noduri din graf.
Functioneaza pe grafuri ponderate cu ponderi pozitive.
Putem să-l folosim pentru a descoperi cel mai scurt drum între două noduri.

dijkstra

void dijkstra(int nod_start){            int* vizitat = new int[nod_maxim+1];    int* tata = new int[nod_maxim+1];    int* dist = new int[nod_maxim+1];    for (int i=1;i<=nod_maxim;i++)        {vizitat[i]=0;dist[i]=999999;tata[i]=-1;}
    int nod_curent=nod_start;    dist[nod_curent]=0;
    while (nod_curent!=-1){        vizitat[nod_curent]=1;        for (nod_lista* pointer = adiacenta[nod_curent].primul_element; pointer !=NULL;pointer = pointer->next){            int vecin=pointer->info;            int d=pointer->pondere;            if (vizitat[vecin]==0 && dist[vecin]>dist[nod_curent]+d){                dist[vecin]=dist[nod_curent]+d;                tata[vecin]=nod_curent;            }        }        //alegerea urmatorului nod        //se poate optimiza cu un heap        int next_nod=-1;        int next_dist=999999;        for (int vecin=1;vecin<nod_maxim;vecin++)            if (vizitat[vecin]==0 && dist[vecin]<next_dist){                next_nod=vecin;                next_dist=dist[vecin];            }        nod_curent=next_nod;    }
    for (int i=1;i<=nod_maxim;i++)        cout<<dist[i]<<" ";    cout<<endl;
    //print drumul cel mai scurt de la nod_start la orice nod_destinatie    int nod_destinatie=6;    while (nod_destinatie!=nod_start){        cout<<tata[nod_destinatie]<<"->"<<nod_destinatie<<endl;        nod_destinatie=tata[nod_destinatie];    }}

Output:
0 1 3 3 2 53->65->32->51->2