Semestrální projekt do předmětu Grafové Algoritmy, III.ročník zimní semestr, 1999-2000
Projekt: GALG2 - nejlevnější kostra grafu
Autor: Zdeněk Šmíd, L97691
[ Prostředí ] [ Jarníkův alg. ] [ Borůvkův alg. ] [ Topologické uspořádání ] [ Hledání komponent ] [ Nejkratší cesty ]

Borůvkův / Hladový algoritmus



   Tento algoritmus popsal profesor Otakar Borůvka. Slouží nám k zjištění nejlevnější kostry grafu a jedná se o modifikaci základního algoritmu.

Popis algoritmu:

   Hrany grafu uspořádáme podle jejich cen do neklesající posloupnosti. Pak je v tomto pořadí probíráme a do postupmě vytvářeného grafu L, který nám reprezentuje kostru, přidáváme ty z nich, které v grafu L nezpůsobí vznik cyklu.

Popis implementace algoritmu:

   Vstupem do funkce algoritmu je graf reprezentovaný strukturou TGraf, výstupem je taktéž graf obsahující pouze hrany kostry nebo v případě nesouvislosti chybové hlášení reprezentované nulovým pointrem NULL. Jsou použita dvě pomocné pole: pole polev, ve kterém je pro každý vrchol zaznamenáné, zda je již zahrnut v kostře a pokud ano, do které komponenty patří a dále pole p1, které nám slouží pro uschování setříděných hran. Pro setřídění hran podle ceny vzestupně je použita funkce Setrid, jejímž vstupem je graf reprezentovaný strukturou TGraf a výstupem je pole obsahující čísla setříděných hran.

Reprezentace grafu

struct THrana {
 int pv;         číslo počátečního vrcholu hrany
 int kv;         číslo koncového vrcholu hrany
 int cena;       cena hrany
};

struct TGraf {
 int nvrch;         počet vrcholů grafu
 int nhran;         počet hran grafu
 THrana *phran;     pointer (pole) hran
};

Funkce Setrid

void Setrid(TGraf *fgraf,int *p1) {
 int i,j;                    pomocné proměnné pro iteraci
 for (i=0; inhran; i++)  inicializace návratového pole
   p1[i]=i;
 int a,b;                        pomocné proměnné
 for (i=0; i<fgraf->nhran-1; i++) {
   a=i;

V tomto cyklu najdeme v aktuálním výběru hranu s nejmenší cenou a po ukončení cyklu ji prohodíme s první hranou výběru.
   for (j=i+1; j<fgraf->nhran; j++)
     if ( fgraf->phran[p1[a]].cena > fgraf->phran[p1[j]].cena)
       a=j;
     b=p1[i];               prohození
     p1[i]=p1[a];
     p1[a]=b;
 }
 return;
}
 Konec fce Setrid


Funkce realizující Borůvkův algoritmus

TGraf *boruvka(TGraf *fgraf) {
 TGraf *rgraf;             návratový graf, alokace paměti
 rgraf=new TGraf;
 rgraf->phran=new THrana[fgraf->nvrch-1];

 int i,k;      pomocné proměnné pro iterační cykly
 int a,b,c;    pomocné proměnné

 int *p1;                     pomocné pole s čísly hran (setříděné)
 p1=new int[fgraf->nhran];
 Setrid(fgraf,p1);

 int *polev;                  pomocné pole vrcholů, jeho inicializace
 polev=new int[fgraf->nvrch];
 for (i=0; i<fgraf->nvrch; i++)
   polev[i]=0;

 b=a=0;   a=cislo hrany v setridenem poli; b=prirustkove cislo komponent (udává maximální identifikační číslo možné existujíci komponenty).
cyklus pro nvrch-1, udává nám počet přidaných hran
 for (k=0; k<fgraf->nvrch-1; k++) {

Pokud nejde o spojitý graf, tzn. že jsme došli na kone pole setříděných hran a přesto nebylo přidáno nvrch-1 hran, dealokujeme paměť a vrátíme chybovou zprávu.
   if (a==fgraf->nhran) {
     delete []rgraf->phran;
     delete rgraf;
     delete []p1;
     delete []polev;
     return NULL;
   }

Pokud ani jeden z vrcholů aktuálně zkoumané hrany není zahrnut ve vytvářeném grafu (u obou je hodnota polev=0), vytvoříme novou komponentu. Hranu pak můžeme bez dalšího testování přidat.
   if ( !(polev[fgraf->phran[p1[a]].pv-1] | polev[fgraf->phran[p1[a]].kv-1]) ) {
     c=++b;    zvětší se nám počet komponent
   }

Pokud je ve vytvářeném grafu jeden vrchol, můžeme hranu bez dalšího testování přidat. Neoznačený vrchol získá číslo komponenty od označené hrany.
   else if ( !(polev[fgraf->phran[p1[a]].pv-1] & polev[fgraf->phran[p1[a]].kv-1]) ) {
     c=polev[fgraf->phran[p1[a]].pv-1] + polev[fgraf->phran[p1[a]].kv-1];
   }

Pokud jsou oba vrcholy označeny, ale leží v různých komponentách, přidáme hranu a pro jednu komponentu přečíslujeme všechny její vrcholy na číslo komponenty první.
   else if (polev[fgraf->phran[p1[a]].pv-1] != polev[fgraf->phran[p1[a]].kv-1]) {
     c=polev[fgraf->phran[p1[a]].pv-1];
     for (i=0; i<fgraf->nhran; i++)
       if (polev[i]==polev[fgraf->phran[p1[a]].kv-1])    test, zda procházený vrchol náleží do druhé komponenty a má se tudíž přečíslovat
         polev[i]=c;             přečíslování druhé komponenty
   }

Pokud neplatí ani jedna z předchozích variant, tzn. že přidáním hrany by vznikl cyklus, přejdeme na další hranu v poli p1.
   else {
     a++;
     k--;
     continue;
   }

Přidání aktuální hrany do pomocného grafu, očíslování příslušných vrcholů číslem příslušné komponenty.
   polev[fgraf->phran[p1[a]].pv-1]=c;
   polev[fgraf->phran[p1[a]].kv-1]=c;
   rgraf->phran[k].pv=fgraf->phran[p1[a]].pv;
   rgraf->phran[k].kv=fgraf->phran[p1[a]].kv;
   rgraf->phran[k].cena=fgraf->phran[p1[a]].cena;
   a++;     přechod na další hranu
 }

Zapsání počtu vrcholů a hran (pro dodržení reprezentace struktury TGraf jako grafu), uvolnění paměti pomocných proměnných a předání kostry grafu uživatelskému prostředí.
 rgraf->nvrch=fgraf->nvrch;
 rgraf->nhran=rgraf->nvrch-1;
 delete []p1;
 delete []polev;
 return rgraf;
}
 Konec funkce boruvka

[ Prostředí ] [ Jarníkův alg. ] [ Borůvkův alg. ] [ Topologické uspořádání ] [ Hledání komponent ] [ Nejkratší cesty ]