Articole

Considerăm un graf neorientat ponderat (cu costuri) conex G. Se numește arbore parțial un graf parțial al lui G care este arbore. Se numește arbore parțial de cost minim un arbore parțial pentru care suma costurilor muchiilor este minimă.

Dacă graful nu este conex, vorbim despre o pădure parțială de cost minim.

Algoritmul lui Kruskal permite determinarea unui arbore parțial de cost minim (APM) într-un graf ponderat cu N noduri.

Descrierea algoritmului

Pentru a determina APM-ul se pleacă de la o pădure formată din N subarbori. Fiecare nod al grafului reprezintă inițial un subarbore. Aceștia vor fi reuniți succesiv prin muchii, până când se obține un singur arbore (dacă graful este conex) sau până când acest lucru nu mai este posibil (dacă graful nu este conex).

Algoritmul este:

• se ordonează muchiile grafului crescător după cost;
• se analizează pe rând muchiile grafului, în ordinea crescătoare a costurilor;
• pentru fiecare muchie analizată:
  • dacă extremitățile muchiei fac parte din același subarbore, muchia se ignoră
  • dacă extremitățile muchiei fac parte din subarbori diferiți, aceștia se vor reuni, iar muchia respectivă face parte din APM.

Principala dificultate în algoritmul descris mai sus este stabilirea faptului că extremitățile muchiei curente fac sau nu parte din același subarbore. În acest scop vom stabili pentru fiecare subarbore un nod special, numit reprezentant al (sub)arborelui și pentru fiecare nod din graf vom memora reprezentantul său (de fapt al subarborelui din care face parte) într-un tablou unidimensional.

Pentru a stabili dacă două noduri fac sau nu parte din același subarbore vom verifica dacă ele au același reprezentant. Pentru a reuni doi subarbori vom înlocui pentru toate nodurile din subarborele B cu reprezentantul subarborelui A.

Înlocuirile descrise mai sus sunt simple dar lente. Pentru o implementare mai eficientă a algoritmului se poate folosi conceptul de Padure de mulțimi disjuncte, descris în acest articol.

Exemplu

Vom determina, folosind Algoritmul lui Kruskal, arborele parțial de cost minim pentru graful de mai jos:

Muchiile se vor analiza în ordinea următoare:

1.		Se adaugă muchia (7,8) de cost 1
2.		Se adaugă muchia (3,9) de cost 2
3.		Se adaugă muchia (6,7) de cost 2
4.		Se adaugă muchia (1,2) de cost 4
5.		Se adaugă muchia (3,6) de cost 1
6.		Se ignoră muchia (7,9) de cost 6
7.		Se adaugă muchia (3,4) de cost 7
8.		Se ignoră muchia (8,9) de cost 7
9.		Se adaugă muchia (1,8) de cost 8
10.		Se ignoră muchia (2,3) de cost 8
11.		Se adaugă muchia (4,5) de cost 9
12.		Se ignoră muchia (5,6) de cost 10
13.		Se ignoră muchia (2,8) de cost 11
14.		Se ignoră muchia (4,6) de cost 14

Secvență C++

Următoarea secvență determină costul total al APM-ului, folosind algoritmul lui Kruskal. Presupunem că graful are cel mult 100 de noduri.

struct muchie{
	int i,j,cost;
};

int n , m , t[101];

muchie x[5000];

int main()
{
    cin >> n >> m;

    for(int i = 0 ; i < m ; ++i)
		cin >> x[i].i >> x[i].j >> x[i].cost;

	//sortare tablou x[] după campul cost
    // ... de completat

    //initializare reprezentanti
	for(int i =1 ; i <= n ; ++i)
		t[i] = i;
      //determinare APM
	int S = 0;
	for(int i = 0 ; i < m ; i ++)
		if(t[x[i].i] != t[x[i].j]) // extremitatile fac parte din subrabori diferiti
		{
			S += x[i].cost;
            //reunim subarborii
			int ai = t[x[i].i], aj = t[x[i].j];
			for(int j =1 ; j <= n ; ++j)
				if(t[j] == aj)
					t[j] = ai;
		}
	cout << S << "\n";
	return 0;
}

Vezi și

• Algoritmul lui Prim

Considerăm un graf neorientat ponderat (cu costuri) conex G. Se numește arbore parțial un graf parțial al lui G care este arbore. Se numește arbore parțial de cost minim un arbore parțial pentru care suma costurilor muchiilor este minimă.

Dacă graful nu este conex, vorbim despre o pădure parțială de cost minim.

Algoritmul lui Prim permite determinarea unui arbore parțial de cost minim (APM) într-un graf ponderat cu N noduri.

Descrierea algoritmului

Determinarea APM-ului se face astfel:

• se stabilește un nod de plecare; acesta va fi rădăcina arborelui, care se va crea pas cu pas, prin adăugarea de noi noduri;
• în mod repetat:
  • se alege un nod neadăugat încă în arborele curent pentru care muchia dintre el și un nod din arbore are cost minim;
  • se adăugă nodul în arbore;
• când nu se mai poate face alegerea unui asemenea nod, fie au fost adăugate toate nodurile, fie graful nu este conex și au fost adăugate în arbore toate nodurile din componenta conexă a nodul inițial;
• dacă graful nu este conex, continuăm cu următoarea componentă conexă.

Observație: arborele parțial de cost minim al unui graf neorientat nu este unic, însă toate APM-urile vor avea același cost.

Exemplu

Mai jos este descris modul în care se aleg nodurile care se adaugă în arbore pentru un graf ponderat cu N=9 noduri:

Algoritmul poate fi implementat în mai multe moduri, cu complexități diferite.

Varianta \(N^3\)

• în mod repetat (de cel mult N-1 ori):
  • se aleg două noduri adiacente, un nod din arbore și un nod din afara acestuia, astfel încât muchia determinată de cele două noduri să aibă costul minim
  • nodul ales din afara arborelui curent se va adăuga în arbore

Varianta \(N^2\)

Față de varianta anterioară se evită căutarea propriu zisă a nodului din arbore, căutându-se efectiv numai nodul din afara acestuia. Pentru aceasta se păstrează un șir d[] cu următoarea semnificație: pentru un nod k încă neadăugat în arbore, d[k] reprezintă costul minim al unei muchii având o extremitate k și o extremitate în arbore; dacă o asemenea muchie nu există d[k] = INFINIT.

Dacă determinarea succesivă a nodurilor din afara arborelui se face prin parcurgerea șirului d[], complexitatea devine O(N2).

Varianta \(N \log N\)

Se poate evita parcurgerea șirului d[] prin memorarea nodurilor din arbore într-o structură de date de tip heap, în vârful heap-ului fiind nodul k pentru care d[k] are valoare minimă. În acest fel complexitatea algoritmului devine O(N logN).

Vezi și

• Algoritmul lui Kruskal