Determinarea arborelui parțial de cost minim

O categorie importanta de grafuri esteaceea in care muchiile sun niste legaturi de tip parinte-fiu. Un astfel de graf se va numi ARBORE.

Respectivd de un alt nod numit Succesor sau fiu al nodului.

* Nodurile sunt organizate pe nivele primul nivel fiind ocupat de nodul radacina. Nodurile de pe ultim nivel se caracterizeaza prin faptul ca din ele nu mai iese nici un arc, si se numesc noduri terminale sau frunze.

Nodurile pot contine o asa informatie utila, carte poate fi de orice tip.

Exemplu: Frunzele arborelui sunt 3, 8, 9. Algoritmul Prim (scris in 1957 si implementat in 1961 de catre Dijkstra) elimina acest neajuns. Se opereaza cu datele din acelasi graf. Se porneste initial, ca si in algoritmul lui Kruskal cu n varfuri izolati (adica de la cele n varfuri, dar fara a fi trasat intre aceste varfuri vre-o muchie), urmand ca pe parcurs aceste varfuri sa fie legate intre ele de arborele cu lungimea minima. Fie G= (X, U) un graf neorientat si conex cu n varfuri.

Fiecare muchie se caracterizeaza printr-un numar intreg asociat, numit cost.

Graful este definit prin matricea costurilor, care fiind foarte asemanatoare cu matricea de adiacenta o va inlocui pe aceasta din urma. Notand matricea costurilor cu A, un element Vom adauga pe rand varfurile grafului la arborele partial. Folosim cei tre vectori -vectorul S, numit vector caracteristic. In timpul constructiei arborelui fiecare element S[i] are valoare 1 daca varful i a fost deja inclus in arborele partial, respectiv 0 in caz contrar. Asadar t initial toate elementele vectorului sunt 0, iar in momentul includerii unui varf I in arbore facem facem s[i]=1; -vectorul T numit vectorul parintilor. Pentru fiecare i care se adauga arborelui, elementul T[i] va reprezenta varful parinte al lui i in arbore.

-vectorul C, numit vectorul costurilor.

Pentru fiecare varf i elementul c[i] va avea valoarea costul muchiei care il leaga de parintele sau in arbore.

Luam in considerare doar michiile care au varf in arborele deja construit si celalat varf in afara arborelui.

Dintre aceste muchii vom alege una care are costul cel mai mic. Legam muchia aleasa in arbore si actualizam vectorii S, T si C. Daca sunt mai multe astfel de muchii care au costul minim, putem alege oricare, de unde rezulta observatia ca arborele partial de cost minim al unui graf nu este unic.

Pentru graful dat exemplu avem initial in arbore varful de start 1 deci la primul pas se iau in considerare muchiile care trec prin varful 1. Pasul 1: initializarea vectorului S[start]=1 start=1; S= T= C= Pasul 2: cautarea urmatoarei muchii: (1, 2) cu costul 13 (1, 3) cu costul 16 (1, 4) cu costul 13 Alegem muchia cu costul minim: muchia (1, 2) pe care o legam in arbore.

Actualizam totodata vectorii caracteristici S, T, C. In arbore a aparut varful 2 fapt pe care-l vom remarca in vectorul caracteristic S[2]: =1. Parintele varfului 2 este varful 1, deci T[2]: =1. Costul muchiei care leaga ...