Vysoká škola báňská - Technická univerzita Ostrava
fakulta elektrotechniky a informatiky
katedra informatiky
Semestrální projekt do předmětu Grafové Algoritmy, III.ročník zimní semestr, 1999-2000
Projekt: GALG2 - topologické uspořádání vrcholů a hran
Autor: Lumír Návrat, L97063
[ Prostředí ] [ Jarníkův alg. ] [ Borůvkův alg. ] [ Topologické uspořádání ] [ Hledání komponent ] [ Nejkratší cesty ]

Algoritmus na topologické uspořádání vrcholů a hran



   Topologické uspořádání vrcholů grafu G je taková posloupnost vrcholů grafu v1, v2, ..., v|V(G)|, že kdykoliv vede orientovaná hrana z vi do vj, platí i < j. Tj. počáteční vrchol kterékoli hrany předchází v topologickém uspořádání koncovému vrcholu této hrany.

   Topologické uspořádání hran grafu G je taková posloupnost hran grafu e1, e2, ..., e|E(G)|, že kdykoliv KV(ei) = PV(ej), platí i < j. Tj. pro každý vrchol v platí, že všechny hrany, které přicházejí do v, předcházejí hranám , které vycházejí z v.

Popis algoritmu:

   Nejprve určíme u všech vrcholů jejich vstupní stupeň, který uložíme do pole těchto vstupních stupňů. Pak všechny vrcholy, které mají nulový stupeň uložíme do pole M. Pokud pole M nebosahuje ani jeden vrchol pak algoritmus skončí. Jinak vezmeme některý vrchol z M a zařadíme jej na konec posloupnosti vrcholů. Nyní každou hranu h takovou, že její počáteční vrchol se rovná právě zařazenému vrcholu provedeme zařazení této hrany na konec posloupnosti hran. Po zařazení ještě musíme provést snížení vstupního stupně koncového vrcholu zařazené hrany. Pokud po snížení je vstupní stupeň vrcholu nulový, pak ho zařadíme do pole M. Pokud je graf acyklický pak se nám podaří ho topologicky uspořádat. V opačném případě algoritmus končí aniž by uložil všechny vrcholy do posloupnosti. Toho lze tím pádem využít k určení acykličnosti grafu.

Popis implementace algoritmu:

   Vstupem do funkce algoritmu je graf reprezentovaný strukturou TGraf a dvě pole PV a PH, které slouží zároveň jako výstup pomocí něhož se předá uspořádáná posloupnost vrcholů a hran. Návratovou hodnotou je celočíselná konstatna určující zda se jedná o acyklický nebo cyklický graf. Jsou použita dvě pomocné pole: pole Vsi, ve kterém jsou vstupní stupně vrcholů a pole M, ve kterém jsou vrcholy s nulovým stupněm. Pole PH neobsahuje přímo hrany, ale jen její index, vzhledem k pořadí v jakém byly zadány.

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í algoritmus na topologické uspořádání vrcholů a hran

int TopologickeUsp(TGraf& graf, int *PV, int *PH)
graf: graf, který se má topologicky uspořádat
PV:   vrací tologicky uspořádanou posloupnost indexů vrcholů
PH:   vrací tologicky uspořádanou posloupnost indexů hran
{
Alokace pole obsahující vstupní stupně vrcholů a jeho nulování.
  int* Vsi = new int[graf.nvrch];
  memset(Vsi,0,graf.nvrch * sizeof(int));
Alokace pole obsahující vrcholy s nulovým vstupním stupněm.
  int* M = new int[graf.nvrch];
  memset(M,0,graf.nvrch * sizeof(int));

Nastavení proměnné určující počet setříděných vrcholů a nulování pole obsahující indexy setříděných vrcholů.
  int pocvrch = 0;
  memset(PV,0,graf.nvrch * sizeof(int));

Nastavení proměnné určující počet setříděných hran a nulování pole obsahující indexy setříděných vrcholů.
  int pochran = 0;
  memset(PH,0,graf.nhran * sizeof(int));

Výpočet vstupních stupňů vrcholů.
  for(int i = 1; i<=graf.nhran;i++)
  {
    Vsi[graf.phran[i-1].kv-1]++;
  }

Všechny vrcholy s nulovým stupněm si uložíme do pole M.
  int numofM = 0;             počet vrcholů v M
  for(i = 1;i<=graf.nvrch;i++)
  {
    if (Vsi[i-1] == 0) M[numofM++] = i;
  }

Hlavní cyklus algoritmu. Provádí se tak dlouho, dokud není počet vrcholů v poli M rovno 0
  while (numofM != 0)
  {
    PV[pocvrch++] = M[0];            Zařadíme vrchol z pole M do PV a zvýšíme počet zařazených vrcholů.
    for( i = 1; i <= graf.nhran;i++)         Procházíme seznam všech hran a testujeme, zda počáteční
      if (M[0] == graf.phran[i-1].pv)       vrchol hrany se rovná právě zařazenému vrcholu.
      {
        PH[pochran++] = i;       Zařadíme hranu do seznamu hran a zvýšíme počet zařazených hran.
        Vsi[graf.phran[i-1].kv-1]--;     Snížíme vstupní stupeň koncového vrcholu hrany.
Jestliže po snížení stupně je stupeň vrcholu 0, pak ho zařadíme na konec pole M.
        if (Vsi[graf.phran[i-1].kv-1] == 0) M[numofM++] = graf.phran[i-1].kv;
      }
Pomocný cyklus, který "setřese" vrcholy v poli M. Následně se sníží počet vrcholů v tomto poli.
    for(int j = 1;j < numofM;j++) M[j-1] = M[j];
    numofM--;
  }
Dealokace pomocných polí
  delete []M;
  delete []Vsi;
Jestliže se počet zařazených vrcholů nerovná počtu vrcholů v grafu, pak se jedná o cyklický graf.
  if (pocvrch != graf.nvrch) return CYKLICKY;
  return ACYKLICKY;
}
 Konec fce TopologickeUsp()

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