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