Topologické triedenie

Základnou operáciou na orientovaných acyklických grafoch (dag-och) je spracovanie vrcholov grafu v takom poradí, že žiaden vrchol nie je spracovaný skôr ako vrchol, ktorý na neho ukazuje. Topologické usporiadanie vrcholov grafu G je také lineárne usporiadanie všetkých jeho vrcholov, že ak G obsahuje hranu (u,v), potom sa u nachádza v tomto usporiadaní pred vrcholom v. Taktiež platí, že ak graf G obsahuje cyklus (nie je dag), tak topologické usporiadanie neexistuje. Rovnako aj opačne.
V praxi sa topologické triedenie používa na plánovanie jednotlivých častí projektu, na vhodné poradie vykonávania jednotlivých podprocesov hlavného procesu a podobne.

^ TOP

Reverzné topologické triedenie

Často potrebujeme interpretovať hrany v grafe naopak, teda hrana (x,y) znamená, že vrchol x závisí na vrchole y. Napriklad pri poradí definícií sa stáva, že jedna definícia sa odvoláva na predchádzajúcu. Takéto usporiadanie sa nazýva reverzné topologické usporiadanie a je ekvivalentné topologickému triedeniu grafu s otočenými orientáciami hrán. Reverzné topologické usporiadanie sa dá jednoducho získať prehľadávaním do hĺbky. Vždy, keď prehľadávanie v rekurzii odchádza z vrcholu, vypíše sa číslo vrcholu a nakoniec sú čísla vrcholov vypísané v reverznom topologickom usporiadaní.

^ TOP

Zápis algoritmu

    int n,g[100][100]; /* graf */
    int saw[100]; /* navštívili sme */
    int nto,torder[100];
    
    void dts_rts(int v)
    {
      int i;
      saw[v]=1;  
      /* prehladame dalsie vrcholy */
      for(i=0;i<n;i++)
        if (g[v][i])
          if(saw[i]==0)
            dfs_rts(i);
      /* pridaj do reverzneho usporiadania */
      torder[nto++]=v;
    }
    
    void tsort(void)
    {
      int i;
      nto=0;
      for(i=0;i<n;i++)
        if (saw[i]==0)
          dfs_rts(i);
      /* hladame topologicke usp. */
      for(i=n-1;i>=0;i--)
        printf("%d\n",torder[i]);
    }
      

^ TOP

Vizualizácia

Topologické usporiadanie grafu z obrázku môže byť nasledovné: J K L M A G H I F E D B C. Iné riešenie je: A J G F K L E M B H C I D.

^ TOP