Povestea arborelui parţial minimal

Prin 1920, Cehia a trecut la electrificare. Motivat de această chestiune practică - acoperirea cu reţea de cabluri electrice a regiunii Moravia - Otakar Borůvka a formulat problema arborelui parţial minimal şi a publicat în 1926, un prim algoritm de rezolvare. În 1930 Vojtěch Jarník a publicat un al doilea algoritm, redescoperit apoi (25 de ani mai târziu) de către Prim.

Avem deci graful G, în care vârfurile reprezintă localităţile (ca şi pe o hartă obişnuită); dacă realitatea terenului face posibilă (din punct de vedere tehnic) construcţia necesară pentru conectarea prin cablu electric a două localităţi oarecare, atunci unim printr-o muchie vârfurile corespunzătoare şi înregistrăm cumva costul estimat pentru realizarea practică a conectării (incluzând pe deviz costul cablului şi costul manoperei, de exemplu).

Fiindcă în final se doreşte conectarea tuturor localităţilor într-o aceeaşi reţea, putem presupune că G este graf conex: se poate ajunge din oricare vârf la oricare altul, trecând eventual prin unele vârfuri intermediare şi folosind desigur, muchiile existente în graf. Iar pentru asigurarea distribuirii energiei electrice către toate localităţile, nu este necesară materializarea tuturor legăturilor considerate iniţial ca posibile; dacă angajăm muchiile A—B, B—C şi C—D atunci este inutil să mai considerăm şi muchia D—A - cu alte cuvinte, vor fi de materializat acele legături care nu conţin cicli (sau "cicluri") şi care, pe de altă parte, asigură un cost total minim pentru lucrările care ar trebui executate.

Astfel că, plecând de la graful conex G, trebuie construit un subgraf al său care să conţină toate vârfurile, să nu conţină nici un ciclu şi să aibă costul cumulat minim (un arbore parţial minimal - "APM" - al lui G).

Algoritmul lui Borůvka a fost influenţat fără doar şi poate, de contextul real în care s-a pus problema - de faptul că lucrările pot demara şi pot fi executate în paralel. Demarând "în paralel", se leagă fiecare vârf cu cel mai apropiat (în privinţa costului conexiunii); considerând celulele rezultate ca "vârfuri", se determină costurile de conectare între acestea şi se leagă ("în paralel") fiecare celulă cu cea mai apropiată ei; ş.a.m.d., până se obţine o singură celulă. Pe baza ideii lui Borůvka, după 1990 au fost creaţi algoritmii cei mai performanţi (vezi de exemplu Tarjan, care a introdus structura de date "heap Fibonacci"; Chazelle, care a inventat structura de date "soft heap").

În schimb, algoritmul lui Jarník-Prim este un algoritm serial: se alege un prim vârf şi se conectează cu vârful care îi este cel mai apropiat; apoi se continuă "recrutarea", adăugând succesiv acel vârf nerecrutat anterior care este cel mai aproape de mulţimea vârfurilor anterior recrutate.

Algoritmul lui Prim - implementare clasică

Lemă. Fie G un graf ponderat conex, astfel încât ponderile (sau "costurile") asociate muchiilor sunt distincte. Fie T o submulţime de vârfuri ale lui G şi fie e muchia de cost minim care conectează un vârf din T cu un vârf din G — T; atunci e face parte din arborele parţial minimal al lui G.

Algoritmul lui Prim se bazează pe această lemă (care se demonstrează uşor) şi poate fi descris astfel:

Fie T mulţimea constituită de un singur vârf (dat iniţial)
while (T nu conţine toate vârfurile) {
    Determină muchia e de cost minim care conectează T cu G — T (vezi Lema)
    (dacă există mai multe astfel de muchii - alege una dintre ele)
    Adaugă muchia e în T
}
În final, T este un APM

În wikipedia, la Prim_algorithm este redată o ilustrare "pas cu pas" şi algoritmul este descris (în "pseudocod") cu implicarea unei structuri de date "min-heap". Iar în manual este redată o implementare care foloseşte o "coadă de prioritate", după modelul din Introduction to algorithms (CLRS, tradusă şi în română). Aici vrem să dăm în primul rând, o implementare "minimală" de bază, desigur cea mai simplă.

Vom folosi C++, anume fie compilatorul g++ din GCC (pe Linux, sau pe Windows), fie bcc32 ("Borland C++ 5.5.1 for Win32") sub Windows; dar desigur, se poate folosi şi Borland C++ 3.1, modificând în prealabil 3 linii din textul sursă de mai jos (vezi comentariile), sau Microsoft Visual C++.

Presupunem că s-a dat graful printr-un fişier text (numărul de vârfuri, de muchii şi apoi fiecare muchie împreună cu ponderea asociată ei). În program vom folosi variabilele globale nr_vf (numărul de vârfuri), nr_eg (de muchii), M[] pentru tabloul muchiilor şi APM[] pentru a indica muchiile care constituie împreună soluţia problemei (aceste două tablouri vor fi alocate în "memoria heap", iar adresele lor vor fi păstrate în zona de date globale); funcţia init() face alocările necesare şi "converteşte" datele din fişierul dat în formatul intern de memorare.

Ca principiu (şi nici nu-i rău!), folosim identificatori "lungi" şi nu de câte o singură literă (desigur, contrar obiceiului instituit în manualele şcolare); am văzut multe persoane care copiază programul şi scriu sau tastează "m" în loc de "n" (iar în final reproşează: "nu dă nimic") - dar desigur, programatorul vrea să sugereze prin identificatorul folosit, raţiunea de a fi a obiectului desemnat.

/* Algoritmul lui Prim (determină un APM într-un graf ponderat conex) */

#include <iostream>   // <iostream.h> pentru Borland C++ 3.1
#include <fstream>   // <fstream.h> pentru Borland C++ 3.1
using namespace std;   // a elimina/comenta, pentru Borland C++ 3.1

ifstream fs("muchii.txt"); // are structura: [ nr. vârfuri ] [ nr. muchii ] [ vf1, vf2, cost ]*

int nr_vf, nr_eg;   // identificatorii "lungi" (în loc de n, m) evită confuzii la copiere!

typedef struct {
    int beg, end; // capetele muchiei
    double cost; 
} muchie;

muchie * M;  // tabloul muchiilor grafului

int * APM;  // rangurile celor (n-1) muchii din M[] alese în APM

void init() {
    fs >> nr_vf >> nr_eg;
    APM = new int[nr_vf - 1];
    M = new muchie [nr_eg]; // main() va trebui să elibereze zonele alocate aici
    for (int i = 0; i < nr_eg; i++) {
        fs >> M[i].beg >> M[i].end >> M[i].cost;
        M[i].beg--; M[i].end--; // în fişier vârfurile 1..n dar în tablou 0..(n-1)
    }
}

Programul nu-i gata… Dar nu vrem doar să redăm programul (ca în manuale, peste tot - parcă te îndeamnă să copiezi!); cine vrea să înveţe "să programeze" trebuie să deprindă obiceiul elementar de a testa porţiunile de program semnificative (contrar obiceiului grosolan de a copia mot-a-mot tot programul). Aţi observat un bucătar gătind ceva? O fi urmând el o reţetă de bază, dar din când în când gustă şi se întreabă dacă nu cumva trebuie să îndrepte sau să adauge ceva…

Acum—în loc de a "scrie" restul programului—ar trebui scrisă funcţia main() în care să se apeleze init() şi să se afişeze conţinutul lui M[], pentru a verifica dacă porţiunea scrisă mai sus este sau nu corectă. Cu cât mai devreme descoperi o greşală, cu atât mai repede vei găsi drumul cel bun (principiu de bază şi în "metoda backtracking").

Ar fi momentul să spunem că de obicei programatorii nu se gândesc de la început la "cea mai bună" soluţie, ci mai întâi la una care "să meargă" (spre deosebire de manuale, unde se redă "cea mai bună" soluţie); ei mizează în compensaţie, pe deprinderea (perfecţionată cumulativ) de a separara lucrurile: modulează programul în aşa fel încât să se poată reveni uşor în punctele "vulnerabile" (sau să poată fi completat / "rescris" uşor).

Să modelăm acum Lema (revezi mai sus) pe care se bazează algoritmul. cut_min() primeşte adresa tabloului în care se vor fi marcat vârfurile "recrutate" deja în APM şi determină acea muchie e din tabloul M[] (sau una dintre ele, dacă sunt mai multe) care are capetele în "tabere" diferite (deja "recrutat" — "nerecrutat") şi care în plus, are costul cel mai mic.

int cut_min(int *Z) { // Z[i] = 1 sau 0, după cum vârful i a fost sau nu vizitat
    int rm; double q = 1.E15; // q este o valoare mai mare decât costurile existente
    for (int i = 0; i < nr_eg; i++)
        if(Z[M[i].beg] ^ Z[M[i].end]) // capetele muchiei să fie din "tabere" diferite (XOR)
            if(M[i].cost < q) {
                rm = i;
                q = M[i].cost;
            }
    return rm; // rangul celei mai "scurte" muchii care uneşte un vârf vizitat cu unul nevizitat
}

void apm_Prim(int start) { // vârful de start (oarecare, când costurile sunt distincte: APM unic)
    int *Z = new int[nr_vf], i;
    for (i = 0; i < nr_vf; i++) // iniţializează vârfurile ca "nerecrutate" în APM
        Z[i] = 0;
    Z[start] = 1; // marchează capătul primei muchii care se va include în APM
    for (i = 0; i < nr_vf - 1; i++) { // un APM conţine nr_vf-1 muchii
        int rm = cut_min(Z);
        APM[i] = rm; // muchia de rang rm este inclusă în APM (a i-a muchie a arborelui)
        if(Z[M[rm].beg])
            Z[M[rm].end] = 1; // marchează şi celălalt capăt al muchiei incluse în APM
        else Z[M[rm].beg] = 1;
    }
    delete [] Z; // eliberează în final, zona alocată pentru Z[]
}

În sfârşit, main() - cu atenţionarea că, probabil pentru Borland C++ 3.1 va trebui scris void main() şi va trebui eliminat return 0 - poate fi scrisă astfel:

int main() { 
    init();
    int i; double cost_apm = 0;
    cout << "vârful de plecare: "; cin >> i;
    apm_Prim(i - 1); // APM[] va conţine rangurile muchiilor selectate în A.P.M.
    for (i = 0; i < nr_vf - 1; i++) { // afişează muchiile din APM şi costurile
        int rm = APM[i];
        cout << (M[rm].beg + 1) << " - " << (M[rm].end + 1) << '\t' << M[rm].cost << '\n';
        cost_apm += M[rm].cost;
    }
    cout<<"\nCostul minim = " << cost_apm << '\n';
    delete [] APM; // alocările le-a făcut INIT(), dar zonele trebuie în final, eliberate!
    delete [] M;
    return 0;
}

Programul nostru e gata, dar programatorul nostru mai are de lucru… Nu-i vorba de a învăţa programul, ci este vorba de a învăţa să programezi! Urmează mai multe operaţii tipice, cam în această ordine: întâi trebuie filat textul programului, recitind rapid (nu "mot-a-mot"!) de sus în jos şi luând aminte la elementele "cheie" (în aşa fel încât, ulterior să-l poţi edita şi singur, fără caiet şi fără carte); urmează apoi operaţiile obişnuite: editează singur programul, filează ca să vezi dacă nu ţi-a scăpat ceva, compilează-l, procură nişte fişiere de date, vezi cum merge pe diverse seturi de date. Vezi şi ce poţi să mai faci, vezi şi ce mai fac alţii… de exemplu, fă o pauză şi vezi ce eficient joacă Nadal (apoi, vezi dacă programul tău este şi el, "eficient").

Compromisuri între stil şi eficienţă

Manualele excelează desigur, în a menţiona peste tot complexitatea algoritmului; programatorul are şi el în vedere cam la fiecare pas eficienţa codului său (dar mai ales în final, că atunci are de unde pleca!).

Mai întâi am putea observa că funcţia cut_min() este apelată din apm_Prim() într-o manieră ineficientă: rm = cut_min( Z ); la apel (şi se fac nr_vf — 1 apelări) se transmite ca parametru pointerul Z; între apeluri este modificat tabloul Z[], dar nu şi adresa lui - încât transmiterea acestui parametru este inutilă. Dar dacă nu s-ar transmite Z, atunci cut_min() n-ar putea accesa tabloul Z[] - fiindcă Z a fost declarat şi alocat în contextul local al funcţiei apelante apm_Prim().

Faptul că tocmai aşa am procedat… ţine de subconştient: cică nu se cade să ridici variabilele auxiliare chiar la acelaşi "rang" cu variabilele care în mod firesc, au natură globală! Acest principiu de "bun-simţ" este fără îndoială bun - altfel ar trebui să întâlnim numai programe formate din două părţi: o zonă de date globale şi funcţia main(), caz în care s-ar câştiga ceva în privinţa eficienţei, dar cu preţul prea mare, al sacrificării clarităţii programului.

Am exagerat, desigur involuntar; mai precis, n-am luat seama la această nuanţă: tabloul este "auxiliar", dar adresa lui - reprezentată de Z - poate fi admisă în rândul variabilelor globale (distincţie subtilă, dar obişnuită: persoanele anonime dintr-o instituţie şi pe de altă parte, reprezentantul nominalizat oficial). Desigur, această distincţie utilă va dispărea dacă se folosesc tablouri statice (în stil "olimpiadistic", obişnuit în manuale).

Prin urmare, dacă vrem neapărat "eficientizare", s-ar impune această corectură simplă: mută declaraţia de pointer int* Z; în zona de date globale (înaintea tuturor funcţiilor). Bineînţeles, nu ne mulţumim noi cu atât; alocarea şi iniţializarea tabloului Z[] fusese făcută în apm_Prim(), dar locul potrivit acum, ar fi în init(). Profităm de împrejurare, pentru a rearanja programul în forma tipică: declaraţii globale, prototipurile funcţiilor folosite, funcţia main(), apoi şi definiţiile funcţiilor (programul este astfel, mai uşor de "citit" de sus în jos).

/* Algoritmul lui Prim (determină un APM într-un graf ponderat conex) */ /* V.5 */

#include <iostream> // cu extensia .h pentru Borland C++ 3.1
#include <fstream>
using namespace std; // a elimina/comenta, în cazul Borland C++ 3.1

ifstream fs("muchii.txt"); // are structura: [ nr. vârfuri ] [ nr. muchii ] [ vf1, vf2, cost ]*
int nr_vf, nr_eg;   // identificatorii "lungi" (în loc de n, m) evită confuzii la copiere!

typedef struct { int beg, end; /* capetele muchiei */ double cost; } muchie;

muchie * M;  // tabloul muchiilor grafului
int * APM;  // rangurile celor (n-1) muchii din M[] alese în APM

int *za; // vizează un tablou auxiliar de "recrutat / nerecrutat" (folosit de mai multe funcţii)

void init(); // internalizează datele din fişier; alocă M[], APM[], za[]
int cut_min(); // care muchie are cost minim, între cele care leagă "taberele" la un moment dat
void apm_Prim(int); // completează APM[], folosind za[] şi cut_min()

int main() { double cost_apm = 0; int i;
    init();
    cout << "vârful de plecare: "; cin >> i;

    apm_Prim(i - 1); // APM[] va conţine rangurile muchiilor selectate în A.P.M.

    for (i = 0; i < nr_vf - 1; i++) { // afişare APM şi cost
        int rm = APM[i];
        cout << (M[rm].beg + 1) << " - " << (M[rm].end + 1) << '\t' << M[rm].cost << '\n';
        cost_apm += M[rm].cost;
    }
    cout << "\nCostul minim = " << cost_apm << '\n';

    delete [] APM; // eliberarea zonelor alocate pentru execuţia curentă
    delete [] M; delete [] za; 
    return 0;
}

void init() {  int i;
    fs >> nr_vf >> nr_eg;
    APM = new int[nr_vf - 1];
    M = new muchie [nr_eg]; // main() va trebui să elibereze zonele alocate aici
    for (i = 0; i < nr_eg; i++) {
        fs >> M[i].beg >> M[i].end >> M[i].cost;
        M[i].beg--; M[i].end--; // în fişier vârfurile 1..n dar în tablou 0..(n-1)
    }
    za = new int[nr_vf]; 
    for (i = 0; i < nr_vf; i++) // iniţializează toate vârfurile ca "nerecrutate" în APM
        za[i] = 0;
}
 
int cut_min() { // za[i] = 1 sau 0, după cum vârful i a fost sau nu "recrutat"
    int rm; double q = 1.E15; // q > costurile existente
    for (int i = 0; i < nr_eg; i++)
        if(za[M[i].beg] ^ za[M[i].end]) // capetele muchiei trebuie să fie din "tabere" diferite
            if(M[i].cost < q) {
                rm = i;
                q = M[i].cost;
            }
    return rm; // rangul celei mai "scurte" muchii care uneşte un vârf vizitat cu unul nevizitat
}
 
void apm_Prim(int start) { // vârful de start (oarecare, când costurile sunt distincte: APM unic)
    za[start] = 1; // marchează capătul primei muchii care se va include în APM
    for (int i = 0; i < nr_vf - 1; i++) {
        int rm = cut_min();
        APM[i] = rm; // muchia de rang rm este inclusă în APM (a i-a muchie a arborelui)
        if(za[M[rm].beg])
            za[M[rm].end] = 1; // marchează şi celălalt capăt al muchiei incluse în APM
        else za[M[rm].beg] = 1;
    }
}

Eficientizarea firească întreprinsă mai sus este importantă, dacă avem în vedere că graful dat ar putea să aibă un ordin mare (nu 20 sau 50 de vârfuri ca în manuale, unde se folosesc tablouri statice); în fond este uşor să generăm aleatoriu grafuri ponderate mari, pe care să testăm comparativ cele două versiuni. Dar "eficientizarea întreprinsă mai sus" este modestă, de ordin practic imediat…

Între eficienţă şi decenţă

Să ne amintim că funcţia cut_min() determină muchia de cost minim dintre muchiile care unesc vârfurile deja "recrutate" cu vârfurile "nerecrutate", angajând pentru aceasta obişnuitul algoritm de aflare a valorii minime.

Să ne imaginăm două apeluri consecutive ale funcţiei cut_min(). La primul s-a produs adăugarea în APM a muchiei [u1, v1], iar la al doilea apel a muchiei [u2, v2]; să presupunem că la intrarea respectivă în cut_min(), vârfurile u erau cele "recrutate" (aveam za[u1] == 1, respectiv za[u2] == 1), iar v-urile erau respectiv, "nerecrutate".

Prin ce diferă cele două mulţimi de muchii - să le notăm Q1 şi Q2 - investigate în fiecare apel de către cut_min()?

În urma primului apel, v1 (şi numai el) trece în grupul vârfurilor "recrutate"; deci Q2 nu mai cuprinde muchia [u1, v1] - care acum, are ambele capete "recrutate" - şi mai general, nu cuprinde muchiile care la primul apel uneau un vârf "recrutat" anterior, cu v1 ("nerecrutat" în acel moment). Exceptând aceste muchii, Q2 conţine toate celelalte muchii din Q1 şi în plus (ca noi elemente faţă de Q1), muchiile [v1, w] cu un capăt în vârful tocmai "recrutat" şi cu w "nerecrutat".

N.B. Poate s-ar cere aici o "poză"… Se poate şi vizualiza raţionamentul, dar chiar n-am folosit vreo poză ajutătoare.

Prin urmare, Q2 "moşteneşte" de la Q1 o submulţime de muchii pentru care deja s-a stabilit costul minim în cursul primului apel (este costul muchiei [u1, v1], al cărei index l-a returnat primul apel); păi atunci, tot ce ar mai avea de făcut "al doilea apel" (în loc să o ia de la capăt, cum face cut_min()) ar fi să afle minimul dintre costul muchiei [u1, v1] şi costurile muchiilor "noi" [v1, w] (cu capătul v1 recrutat de primul apel şi cu celălalt w nerecrutat).

Pentru a putea proceda astfel, cut_min() ar trebui să cunoască ultimul vârf recrutat v1, precum şi ultimul "cost minim" determinat (costul muchiei [u1, v1], vezi mai sus). Dacă ar fi numai atât, ar fi uşor de modificat programul existent (fie şi acceptând încă două variabile globale, pentru vârful curent recrutat şi pentru costul ultimei muchii adăugate în APM); dar trebuie să luăm în consideraţie încă un aspect: cut_min() trebuie acum să investigheze muchiile [v1, w], adică am avea nevoie în mod firesc de lista adiacenţilor lui v1.

Dar nu mai poate fi vorba de "eficientizare", dacă cerem lui cut_min() să şi determine lista adiacenţilor vârfului (la fiecare apel); iar programul a fost construit consecvent, pe baza reprezentării grafului prin tabloul muchiilor şi nu prin liste de adiacenţă (sau prin "matricea costurilor").

Este posibilă (şi nici nu-i dificilă) "salvarea" programului existent: adăugăm ca variabilă globală un pointer int** A; pe care init() să aloce corespunzător şi să constituie (la citirea muchiilor din fişier) matricea de adiacenţă a grafului; folosind matricea A[][], funcţia cut_min() va putea să "vadă" adiacenţii nerecrutaţi ai vârfului v1.

Dar salvarea în acest fel cam atinge insuportabilul… Graful nostru ar fi reprezentat şi prin M[] (unde avem muchiile şi costurile lor) şi prin matricea de adiacenţă A[][], ceea ce este deja indecent (aceste două structuri pot fi înlocuite cu "matricea costurilor", de exemplu). Spre deosebire de situaţia precedentă, de data aceasta nu ajung "micile compromisuri" în programul existent; acesta trebuie mai degrabă abandonat şi trebuie rescris complet, bazându-l acum pe o structură de date adecvată (eventual, de genul matricei costurilor).

Strategia evitării impasului (biblioteci şi interfeţe)

Impasul evidenţiat mai sus se datorează incompatibilităţii între tipul de date asumat iniţial de programul pe care acum am vrea să-l modificăm şi tipul de date de care ar fi fost nevoie acum pentru funcţia cut_min(); cum îţi proiectezi datele (mai bine sau mai rău), aşa vei avea programul!

Şi trebuie reproiectată structura datelor, de la problemă la problemă după caz, chiar dacă problemele vizează o aceeaşi categorie de obiecte… Acesta este spiritul majorităţii manualelor; câte probleme şi algoritmi de grafuri ai în manual - tot atâtea programe de implementare; fiecare program modelează datele în propriul context, prevede propriile funcţii de citire/scriere şi desigur, rezolvă sarcina specificată în enunţ. La fel am procedat aici în programul de mai sus; dar în compensaţie ne-am străduit să evidenţiem şi "cum ar proceda programatorul".

Având "de implementat" algoritmul lui Prim, sau oricare altă problemă cu grafuri - programatorul vede întâi şi întâi acest fapt: are de lucrat cu grafuri. Prin urmare întâi şi întâi îşi procură instrumentele necesare lucrului cu grafuri: şabloane de reprezentare internă, diverse funcţii de citire/scriere şi de conversie între diverse reprezentări, eventual şi nişte funcţii pentru asigurarea unei depanări comode a viitoarelor programe cu grafuri. Programatorul ştie că se pot pune diverse alte probleme cu grafuri şi procedează în aşa fel încât să-şi asigure posibilitatea de a refolosi instrumentele pe care le-a creat (scutindu-se de a le recrea pentru fiecare nouă problemă cu grafuri).

Dar mai mult, programatorul ştie că nu este singur (chiar şi dacă nu are conştiinţa lucrului "în echipă", cum clamează pe deasupra manualele noastre mai noi); şi alţi programatori vor fi avut de rezolvat probleme pe grafuri (iar aceştia cu siguranţă, au procedat la fel: întâi şi-au creat instrumentele necesare lucrului pe grafuri) - trebuie să fie pe undeva o bibliotecă pentru modelarea lucrului cu grafuri…

De fapt, ideea de a folosi o bibliotecă adecvată o şi vedem la tot pasul: dacă sunt de "scris" atâtea şi atâtea programe cu şiruri de caractere, ce faci - scrii tu în fiecare program şi de fiecare dată, funcţiile necesare lucrului cu şiruri?! Nu… pur şi simplu foloseşti #include string.h, adică asiguri importarea în program a unei biblioteci de lucru cu şiruri; vezi ce funcţii îţi sunt necesare şi poţi trece direct la rezolvarea problemei, fără să "pierzi timpul" cu remodelarea "personală" a acelor funcţii.

Însă în manuale, ideea apare numai la nivel tacit; dacă schimbi contextul "şiruri de caractere", cu "numere mari", sau cu "grafuri" atunci manualele refuză parcă, să mai vadă vreo legătură cu "biblioteca"… Ne amintim că în manualele ceva mai vechi (dar n-aş zice "învechite", dimpotrivă - parcă astea mai noi sunt învechite!) se modelau "numerele complexe"—exemplificând programare orientată pe obiecte, ceva parcă "învechit" pentru manualele "noi"—fără să observe însă, că există deja o bibliotecă complex.h.

Aşa cum există şi folosim string.h şi complex.h pentru lucrul cu "şiruri de caractere" şi respectiv, pentru "numere complexe" - există şi biblioteci consolidate pentru modelarea diverselor alte categorii de obiecte, de exemplu pentru "numere mari" (am dat şi noi exemplificări în "Hello World!"), pentru "liste înlănţuite" (#include <list>, ori #include <stack>, etc.), pentru "mulţimi" şi chiar pentru "grafuri".

Pentru un exemplu, iată cum putem folosi direct o coadă de prioritate (a cărei modelare ad-hoc apare mai mult sau mai puţin explicit, în programul de implementare a algoritmului lui Prim, în diverse manuale):

#include <iostream>
#include <queue>  // structuri de "coadă", inclusiv "priority_queue"
using namespace std;

double cost[] = { 11.5, 7, 8, 15, 22, 1, 17, 5, 11.5, 12, 7.2, 5, 1, 20 };

int main() {
    priority_queue<double> PQ; // coadă de prioritate ("primul" e cel mai mare, dat de top()) 
    for(int i = 0, n = sizeof(cost)/sizeof(cost[0]); i < n; i++)
        PQ.push(cost[i]);  // adaugă ("push") în coadă
    while(!PQ.empty()) {
        cout << PQ.top() << ' '; // afişează "primul" element (cel mai mare)
        PQ.pop(); // descarcă "primul" din PQ; apoi "top()" dă cel mai mare dintre cele rămase
    }
}
/* se afişează: 22 20 17 15 12 11.5 11.5 8 7.2 7 5 5 1 1
în conformitate cu regula "întâi cel mai mare" */

Să ne amintim de cut_min() prin care determinam muchia de cost minim (implementând efectiv algoritmul clasic de aflare a minimului); ea poate fi "înlocuită" printr-o priority_queue<double> (completând însă şi cu o funcţie de comparaţie, pentru a forţa ordinea "primul—cel mai mic"). Minimul s-ar obţine "automat", invocând metodele top() şi pop() ale cozii; în plus, <queue> garantează un necesar de cel mult log(N) comparaţii pentru menţinerea ordinii (mult sub cele N comparaţii cerute de algoritmul clasic de aflare a minimului).

Pentru ordinea tocmai invocată "primul—cel mai mic", PQ putea fi declarată cel mai simplu, astfel:

    priority_queue<double, vector<double>, greater<double> > PQ;
  ... 
// se va afişa: 1 1 5 5 7 7.2 8 11.5 11.5 12 15 17 20 22

Avem de-a face cu un tip parametrizat de date: putem avea PQ cu valori int, sau unul cu valori double (sau cu un alt tip de valori), bazat pe un operator de comparaţie (implicit less) sau altul (greater), etc. Genericitatea şi extensibilitatea sunt caracteristici de bază ale bibliotecii STL Standard Template Library (care face parte din C++, de prin 1995), iar priority_queue este o clasă C++ definită în STL.

În deceniul 1990—2000 grafurile (cu tot ce înseamnă ele) au fost acoperite prin biblioteci C++ performante (LEDA şi boost) şi s-au creat modele utile - mai accesibile, pentru nevoi de nivel mediu - şi în alte limbaje (de exemplu modulul Perl Graph, pachetul Python NetworkX). Datorită acestor biblioteci standardizate, programatorii se pot scuti de a reimplementa de fiecare dată structurile de date şi algoritmii tipici pe grafuri, putând acum să lucreze programele în care au de angajat grafuri după principiul Algoritm + LEDA = Program (LEDA desemnând una din bibliotecile standardizate pentru tipuri de date şi algoritmi de teoria grafurilor). Aceste biblioteci excelează în privinţa genericităţii şi parametrizării modelării.

În fond, tocmai de "parametrizare" era nevoie, pentru ca programul nostru să nu depindă aşa de mult de tipurile de date globale! Noi am folosit prototipul void apm_Prim(int start), astfel că singura condiţie cerută din partea funcţiei este aceea de a primi start; altfel spus, pentru variabilele externe pe care le foloseşte, ea asumă în mod tacit că ele ar corespunde manierei interne de folosire. Însă mult mai sigur este ca funcţia să specifice spre exterior de la bun început, ce ipoteze asumă asupra variabilelor externe pe care le foloseşte.

Repetăm: primul lucru de făcut este modelarea corespunzătoare a datelor, sau şi mai bine, importarea unei biblioteci adecvate; apoi, programatorul se ocupă de prototipul funcţiei care implementează algoritmul său - şi el nu va alege void apm_Prim(int start) cum am făcut noi, ci va alege ceva de genul muchie * apm_Prim( muchie** M, int start), adică explicitează "ipotezele de lucru": funcţia apm_Prim trebuie să primească un pointer la "matricea costurilor" şi un vârf de start şi atunci, va returna un pointer la APM.

Odată conceput prototipul funcţiei, acesta trebuie documentat: ce primeşte, ce returnează. Procedând astfel, programatorul aproape că scapă de griji: nu va trebui să-şi modifice codul în funcţie de datele clientului, ci invers - cel care scrie main()-ul, va trebui să-şi definească datele în conformitate cu specificaţiile din interfaţa funcţiei pe care vrea să o utilizeze. În fond… la fel trebuie să procedezi şi pentru a exploata un instrument casnic: pentru a obţine rezultatul scontat trebuie să respecţi parametrii şi instrucţiunile de folosire, furnizate odată cu aparatul.

De altfel, interfaţarea funcţiei faţă de contextul în care este ea creată este utilizată şi în unele manuale. De exemplu "Introduction to algorithms" (2ed, MIT, 2001) introduce pseudocodul pentru algoritmul lui Prim (şi analog pentru toţi algoritmii prezentaţi) prin antetul MST-PRIM(G, w, r), similar prototipului vizat mai sus. Şi desigur, regăsim această manieră de interfaţare în orice bibliotecă; de exemplu, în string.h găsim funcţia int strcmp(const char* s1, const char* s2); prin care se obţine rezultatul comparării a două şiruri.