Tehnici avansate de programare

     Algoritmul lui Kruskal este un algoritm în teoria grafurilor care găsește arborele parțial de cost minim pentru un graf conex ponderat. Cu alte cuvinte, găsește submulțimea muchiilor care formează un arbore care include toate vârfurile și care este minimizat din punct de vedere al costului. Dacă graful nu este conex, atunci algoritmul găsește o pădure parțială de cost minim (un arbore parțial de cost minim pentru fiecare componentă conexă). Algoritmul lui Kruskal este un exemplu de algoritm greedy.

     Algoritmul funcționează în felul următor:                                                                                                                                   

•  creează o pădure F (o mulțime de arbori), unde fiecare vârf din graf este un arbore separat

• creează o mulțime S care conține toate muchiile din graf

• atât timp cât S este nevidă

  • elimină o muchie de cost minim din S

  • dacă acea muchie conectează doi arbori distincți, atunci adaugă muchia în pădure, combinând cei doi arbori într-unul singur

  • altfel, ignoră muchia

     La sfârșitul algoritmului, pădurea are doar o componentă care reprezintă un arbore parțial de cost minim al grafului.

     Acest algoritm a fost scris de Joseph Kruskal, în 1956.

 

     Implementarea algoritmului

 

 

Pentru implementarea algoritmului este necesară rezolvarea următoarelor două probleme:   

– cum extragem muchia de cost minim.    

 – cum testăm dacă muchia selectată formează sau nu cicluri cu cele deja selectate.

Pentru a extrage minimul, o idee ar fi să sortăm muchiile crescător după cost şi să parcurgem secvenţial muchiile ordonate. Pentru a realiza sortarea muchiilor grafului, vom reprezenta graful prin lista muchiilor (un vector cu m componente, fiecare componentă fiind o structură în care reţinem cele două extremităţi şi costul muchiei).

O muchie va forma cicluri cu muchiile deja selectate dacă şi numai dacă între extremităţile muchiei există cel puţin un lanţ.

Pentru a testa dacă o muchie formează cicluri cu muchiile deja selectate este suficient să testăm dacă extremităţile muchiei se găsesc în aceeaşi componentă conexă. Pentru aceasta va trebui să ţinem permanent evidenţa componentelor conexe (arborilor) care se formează.

 

 

 

     Aplicatie practica

 

Trebuie sa conectam 3 orase la o retea telefonica: Bucuresti, Timisoara si Arad.

Necesar cablu: 1300 km.

                                                                                                                                                            

 

                                                          

 

 

 

                       

 

 

 

 

E inutil sa executam toate cele trei conexiuni, numai doua din ele sunt suficiente pentru o comunicare in bune conditii intre oricare 2 orase.

De exemplu, legatura Timisoara – Arad ar putea lipsi, caz in care necesarul de cablu devine 1240 km.

 

 

                                    

 

 

                                

                                          

                                      

 

 

 

 

 

 

Sau legatura Timisoara – Bucuresti ar putea lipsi, necesarul de cablu devenind 700 km.

 

 

 

 

                                        

 

 

 

                                                                                                      

 

 

 

 

Oricare 2 legaturi sunt suficiente, deoarece semnalul electric circula suficient de rapid ca un abonat din Timisoara care doreste sa vorbeasca cu unul din Arad (de exemplu) sa nu-si dea seama ca nu exista legatura directa intre Timisoara si Arad si ca apelul sau este rutat prin Bucuresti.

Din punctul de vedere al necesarului de cablu, lucrurile nu mai stau la fel.

Conteaza foarte mult care legaturi vor fi realizate si care nu.

Cel mai ieftin ar fi sa alegem legaturile Arad – Timisoara si Timisoara – Bucuresti si sa evitam legatura Arad - Bucuresti, necesarul de cablu ajungand in acest caz la 660 km; aceasta este situatia optima – sau “acoperirea minima” a retelei. 

 

 

     Aplicatie

 

Un om vrea să viziteze un număr de n oraşe. Iniţial acesta se află într-unul din ele, notat 1. Omul doreşte să nu treacă de două ori prin acelaşi oraş iar la întoarcere să revină în oraşul 1. Cunoscând legăturile existente între oraşe, se cere lungimea minimă posibilă a drumului pe care îl poate efecta omul.

 

     C++

 

#include <iostream>
#include <fstream>
using namespace std;

//declararea variabilelor
struct muchie{int x,y; float cost;};
muchie b[30],aux;
int n,m,i,k,ct,l[30],j;

//citirea din fisiser a datelor
//n=nr.nodurilor, m=nr. muchiilor, cost=costul fiecarei muchii
void citire() {
    ifstream f ("intrare.txt");
    f>>n>>m;
    for (i=1; i<=m; i++)
        f>>b[i].x>>b[i].y>>b[i].cost;
    f.close();
}

//ordonarea muchiilor dupa cost
void ordonare () {
    for(i=1;i<m;i++)
        for(j=i+1;j<=m;j++)
            if(b[i].cost>b[j].cost) {
                aux=b[i];
                b[i]=b[j];
                b[j]=aux;
            }
}

int main(){
    citire();
    for(i=1;i<=n;i++) l[i]=i; // considerăm că fiecare nod constituie un arbore => vectorul auxiliar l (pădure cu n arbori)
    ordonare();
    k=0; // nr. de muchii selectate
    ct=0; // costul total
    i=1;
    ofstream g ("iesire.txt");
    while(k<n-1) {
        if(l[b[i].x]!=l[b[i].y]) { //se verifică ca muchia să nu închidă un ciclu
            k++; // se selecteaza muchia respectiva
            ct+=b[i].cost; //se adaugă costul muchiei la costul inițial
            for(j=1;j<=n;j++) //se parcurge vectorul auxiliar
                if(l[j]==l[b[i].x]) //se verifică dacă cele două muchii fac parte din aceeași componentă conexă
                    l[j]=l[b[i].y];
            g<<b[i].x<<" "<<b[i].y<<endl; //se afișează muchia
        }
        i++; //se trece la următoarea muchie
    }
    g<<"Costul total = "<<ct<<endl;
    g.close();
    return 0;
}