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 ]

Jarníkův algoritmus

Algoritmus je pojmenován podle známého českého matematika profesora Vojtěcha Jarníka. Slouží nám k zjištění nejlevnější kostry grafu a jedná se o modifikaci základního algoritmu.

Popis algoritmu:

Začneme z libovolného vrcholu a postupně k němu přidáváme vrcholy a hrany tak, že v každé fázi výpočtu máme strom. Přidávanou hranu přitom vždy vybíráme tak, aby měla nejmenší cenu z množiny W_G(A)(všechny hrany, které mají jeden krajní vrchol v množině A a druhý v V(G)-A), kde A je množina vrcholů. V případě, že je původní graf nesouvislý, nemůže vzniknout kostra a výstupem z algoritmu je chybové hlášení.

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 pole p1, které nám slouží jako dočasné pro uschování čísel hran, které budeme dále zpracovávat.

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 realizující Jarníkův algoritmus


TGraf *jarnik(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;

pomocné proměnné





  int *p1;

pomocné pole s čísly hran, alokace paměti



  p1=new int[fgraf->nhran];



  int *polev;

pomocné pole vrcholů udávající, zda je daný vrchol zahrnut v kostře (1) či ne (0), jeho inicializace



  polev=new int[fgraf->nvrch];

  polev[0]=1;

jako výchozí vrchol si vybereme první vrchol



  for (i=1; i<fgraf->nvrch; i++)

    polev[i]=0;

cyklus pro nvrch-1, udává nám počet přidaných hran



  for (k=0; k<fgraf->nvrch-1; k++) {

    a=0;

inicializace, tato proměnná udává, zda byla nalezena odpovídající hrana (viz níže)






Následující cyklus projde všechny hrany a najde ty, které jsou incidentní s právě jedním vrcholem z existujícího stromu, počet hran už přidaných je vzhledem k počtu zbývajícíh zřejmě mnohem menší a proto procházíme i jimi (nedojde ke zpomalení). Čísla těchto hran pak uloží do pomocného pole p1.

    for (i=0; i<fgraf->nhran; i++)

      if ( polev[fgraf->phran[i].pv-1] ^ polev[fgraf->phran[i].kv-1] )

bitový XOR



        p1[a++]=i;

zapise cislo hrany do pomocneho pole





    if (a==0) {

pokud není nalezena žádná hrana a není ještě přidáno nvrch-1 hran => graf je nesouvislý



      delete []rgraf->phran;

uvolnění paměti



      delete rgraf;

      delete []p1;

      delete []polev;

      return NULL;

fce vrací chybovou hodnotu



    }

    b=0;




Proběhne vybrání hrany z pole p1 z nejmenší cenou

    for (i=1; i<a; i++) {

      if (fgraf->phran[p1[b]].cena > fgraf->phran[p1[i]].cena)

        b=i;

v proměnné b je pozice hrany v poli p1 s aktuálně nejmenší cenou



    }




Přidání hrany z pole p1 o nejmenší ceně do pomocného grafu, přidání vrcholů incidentnich s danou hranou do kostry pomocí pole polev.

    polev[fgraf->phran[p1[b]].pv-1]=1;

    polev[fgraf->phran[p1[b]].kv-1]=1;

    rgraf->phran[k].pv=fgraf->phran[p1[b]].pv;

    rgraf->phran[k].kv=fgraf->phran[p1[b]].kv;

    rgraf->phran[k].cena=fgraf->phran[p1[b]].cena;

  }

Konec cyklu přídávání k-té hrany





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 fce jarnik()

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