Tehnici avansate de programare

     Algoritmul lui Prim:

 

         Este un algoritm care returnează un arbore de acoperire minim pentru un graf ponderat (graf în care fiecare arc are asociat un cost), asemenea algoritmului lui Kruskal.

         Un arbore de acoperire pentru un graf este un subgraf alcătuit din toate nodurile grafului inițial dar nu din toate arcele, ci doar din atâtea arce cât să nu apară cicluri (altfel nu va mai fi arbore).

 

     Mod de aplicare:

 

• Inițial, toate nodurile grafului se consideră nevizitate;

• Se pornește de la un nod oarecare al grafului care se marchează ca vizitat;

• In permanență vor fi menținute doua mulțimi:

  • Mulțimea U a nodurilor vizitate (inițial, U va conține doar nodul de start);

  • Mulțimea N\U a nodurilor nevizitate (N este mulțimea tuturor nodurilor);

• La fiecare pas se alege acel nod din mulțimea N\U care este legat prin arc de cost minim de oricare din nodurile din mulțimea U;

• Nodul ales va fi scos din mulțimea N\U si trecut in mulțimea U;

• Algoritmul continuă până când U = N.