Arbori (arbori binari, parcurgeri, arbori partiali – Kruskal, Prim)

Un arbore este un graf neorientat, conex si aciclic. Proprietatile fundamentale: un arbore cu n noduri are exact n-1 muchii; introducerea unei muchii suplimentare creaza un ciclu, iar eliminarea unei muchii deconecteaza graful. In informatica, arborii binari sunt structuri ierarhice in care fiecare nod are cel mult doi descendent (stanga si dreapta).

Parcurgerile uzuale sunt: in-ordine (stanga, radacina, dreapta), pre-ordine (radacina, stanga, dreapta) si post-ordine (stanga, dreapta, radacina). Pentru arbori binari de cautare (BST), in-ordine produce elementele sortate. Arborii partiali (minimum spanning tree - MST) sunt subgrafuri care pastreaza conexitatea si minimizeaza suma costurilor muchiilor.

Algoritmul lui Kruskal sorteaza muchiile crescator si le adauga daca nu formeaza ciclu (folosind Union-Find). Algoritmul lui Prim porneste de la un nod si extinde arborele alegand muchia de cost minim care conecteaza un nod din arbore cu unul din afara. Ambele sunt greedy si au complexitate O(E log E) (Kruskal) respectiv O(V^2) sau O(E log V) (Prim).

La bac, se cer parcurgeri in arbori binari, implementari in pseudocod sau C++, si aplicarea algoritmilor Kruskal si Prim pe grafuri concrete.

Exemple

• Exemplul 1: Arbore binar cu radacina 10, stanga 5 (cu stanga 2, dreapta 7), dreapta 15 (cu stanga 12, dreapta 20). Parcurgeri:
• Pre-ordine: 10, 5, 2, 7, 15, 12, 20.
• In-ordine: 2, 5, 7, 10, 12, 15, 20 (sir sortat).
• Post-ordine: 2, 7, 5, 12, 20, 15, 10.
• Exemplul 2: Graf cu nodurile {A,B,C,D} si muchiile (AB=1, AC=4, BC=2, BD=5, CD=3). Aplicam Kruskal: sortezi muchiile (1,2,3,4,5). Adaugi AB(1), BC(2) – nu formeaza ciclu. Urmatoarea e CD(3) – adaugi, dar acum ai 3 muchii pentru 4 noduri, tot fara ciclu. Muchiile AC(4) si BD(5) sari deoarece ar crea cicluri. MST = {AB, BC, CD} cu cost total 6.
• Exemplul 3: Acelasi graf ca mai sus, pornim cu Prim din A. Se adauga A in arbore. Muchii disponibile: AB(1), AC(4). Se alege AB(1). Acum arbore contine {A,B}. Muchii: AC(4), BC(2), BD(5). minim = BC(2) -> adaug. Arbore: {A,B,C}. Muchii: AC(4) – ignoram (ciclu), BD(5), CD(3). minim = CD(3). Final: muchii AB, BC, CD, cost 6.

Concepte cheie: Arbore: graf conex, aciclic, n noduri si n-1 muchii, Arbore binar: fiecare nod are cel mult 2 fii; parcurgeri in-ordine, pre-ordine, post-ordine, Arbore partial de cost minim (MST): algoritmi Kruskal si Prim, baza greedy, Union-Find pentru detectarea ciclurilor in Kruskal, Complexitati: Kruskal O(E log E), Prim O(E log V) cu heap