Structuri de Date 2023 - C11: Grafuri 2

Structuri de Date

Curs 11: Grafuri 2

Cuprins:

Disjoint Set Forest (pădure de mulțimi disjuncte)
Algoritmul lui Kruskal
Algoritmul lui Prim

1. Disjoint Set Forest (pădure de mulțimi disjuncte)

Mulțimi bazate pe reprezentanți

Reprezentanți ierarhici

DSF este nimic altceva decât vector de tați.

Există 2 operații:

find
union

+ 2 euristici:

Union by Rank
Path Compression

class DSF {    int* parent;    int* rank;
public:    DSF(int n){        parent = new int[n];        rank = new int[n];
        for (int i = 0; i < n; i++) {            parent[i] = -1;            rank[i] = 1;        }    }
    int find(int i){        if (parent[i] == -1)            return i;
        return parent[i] = find(parent[i]);    }
    void unite(int x, int y){        int s1 = find(x);        int s2 = find(y);
        if (s1 != s2) {            if (rank[s1] < rank[s2]) {                parent[s1] = s2;            } else if (rank[s2] < rank[s1]){                parent[s2] = s1;            } else {                parent[s2] = s1;                rank[s1] += 1;            }        }    }};

Path Compression

=când caut reprezentantul unui element, toate elementele parcurse până la reprezentant devin fii direcți ai reprezentantului

Union by Rank

=Reprezentantul mulțimii de rank mic devine fiul mulțimii de rank mare.

Rank = margine superioară pentru distanța până la cel mai departe fiu

(path compression reduce rank-ul fără posibilitatea de recalculare)

2. Algoritmul lui Kruskal

Se începe cu un graf cu n vârfuri dar fără muchii. Dorim să creăm un arbore parțial de cost minim adăugând n-1 muchii.

Se sortează muchiile după pondere.
Se adaugă la arborele parțial de cost minim muchia de cost minim care nu produce cicluri. (Adică nu are voie să aibă ambele capete în același arbore)

Graf complet în care ponderea este distanța euclidiană

struct graf{    lista adiacenta[200];//cate o lista cu vecinii fiecarui nod din graf    int nod_maxim=0;//cand parcurgem sa stim pana la ce nod ne uitam
    void adauga_muchie(int nod_sursa, int nod_destinatie, int pondere){        adiacenta[nod_sursa].insert_la_final(nod_destinatie,pondere);        if (nod_maxim<nod_sursa)            nod_maxim=nod_sursa;        //PENTRU GRAF NEORIENTAT:        adiacenta[nod_destinatie].insert_la_final(nod_sursa,pondere);        if (nod_maxim<nod_destinatie)            nod_maxim=nod_destinatie;    }
    void kruskal(){
        min_heap h;        for (int i=0; i<=nod_maxim;i++)            for (nod_lista* pointer = adiacenta[i].primul_element; pointer !=NULL;pointer = pointer->next)                if (i<pointer->info){//ca sa luam muchiile o singura data                    muchie m(i,pointer->info,pointer->pondere);                    h.insert_heap(m);            }
        DSF multimi(nod_maxim+1);        while(h.n>0){            muchie m=h.extract_heap();            if (multimi.find(m.sursa)!=multimi.find(m.destinatie)){                cout<<m.sursa<<"-"<<m.destinatie<<endl;                multimi.unite(m.sursa,m.destinatie);            }        }
    }

    void afisare(){        for (int i=0; i<=nod_maxim;i++){            if (adiacenta[i].primul_element!=NULL){                cout<<i<<" : ";                adiacenta[i].afisare();            }        }    }
};
int main(){
    graf G;    G.adauga_muchie(1,2,7);    G.adauga_muchie(1,4,5);    G.adauga_muchie(2,3,8);    G.adauga_muchie(2,4,9);    G.adauga_muchie(2,5,7);    G.adauga_muchie(3,5,5);    G.adauga_muchie(4,5,15);    G.adauga_muchie(4,6,6);    G.adauga_muchie(5,6,8);    G.adauga_muchie(5,7,9);    G.adauga_muchie(6,7,11);
    G.kruskal();
    return 0;}

Output:
1-43-54-61-22-55-7

3. Algoritmul lui Prim

Se inițializează arborele parțial de cost minim cu orice vârf.
Creștem arborele cu 1 muchie: dintre muchiile care conectează arborele curent de un nod care nu este încă în arbore, alegem muchia de cost minim.
Repetă 2 până când arborele conține toate vârfurile.

Graf complet în care ponderea este distanța euclidiană

struct graf{    lista adiacenta[200];//cate o lista cu vecinii fiecarui nod din graf    int nod_maxim=0;//cand parcurgem sa stim pana la ce nod ne uitam
    void adauga_muchie(int nod_sursa, int nod_destinatie, int pondere){        adiacenta[nod_sursa].insert_la_final(nod_destinatie,pondere);        if (nod_maxim<nod_sursa)            nod_maxim=nod_sursa;        //PENTRU GRAF NEORIENTAT:        adiacenta[nod_destinatie].insert_la_final(nod_sursa,pondere);        if (nod_maxim<nod_destinatie)            nod_maxim=nod_destinatie;    }
int cel_mai_aproape_nod_care_inca_nu_e_in_arbore(int* dist, int* este_in_arbore){    int min = 999999, min_index;
    for (int i=1; i<=nod_maxim;i++)        if (este_in_arbore[i] == 0 && dist[i] < min)            min = dist[i], min_index = i;
    return min_index;}
    void prim(int nod_start){        int* este_in_arbore = 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++)            {este_in_arbore[i]=0;dist[i]=999999;tata[i]=-1;}
        dist[nod_start]=0;
        for (int i=1;i<=nod_maxim-1;i++){
            int nod=cel_mai_aproape_nod_care_inca_nu_e_in_arbore(dist,este_in_arbore);            este_in_arbore[nod]=1;
            for (nod_lista* pointer = adiacenta[nod].primul_element; pointer !=NULL;pointer = pointer->next){                int vecin=pointer->info;                int d=pointer->pondere;                if (este_in_arbore[vecin]==0 && dist[vecin]>d){                    dist[vecin]=d;                    tata[vecin]=nod;                }            }        }
        for (int i=1;i<=nod_maxim;i++)            if (i!=nod_start)                cout<<tata[i]<<"-"<<i<<endl;    }
    void afisare(){        for (int i=0; i<=nod_maxim;i++){            if (adiacenta[i].primul_element!=NULL){                cout<<i<<" : ";                adiacenta[i].afisare();            }        }    }
};
int main(){
    graf G;    G.adauga_muchie(1,2,7);    G.adauga_muchie(1,4,5);    G.adauga_muchie(2,3,8);    G.adauga_muchie(2,4,9);    G.adauga_muchie(2,5,7);    G.adauga_muchie(3,5,5);    G.adauga_muchie(4,5,15);    G.adauga_muchie(4,6,6);    G.adauga_muchie(5,6,8);    G.adauga_muchie(5,7,9);    G.adauga_muchie(6,7,11);
    G.prim(1);
    return 0;}

Output:
1-25-31-42-54-65-7