Topologické řazení: Python, C++ Příklad algoritmu

Co je topologický třídicí algoritmus?

Topologické třídění je také známé jako Kahnův algoritmus a je oblíbeným třídicím algoritmem. Pomocí orientovaného grafu jako vstupu topologické řazení seřadí uzly tak, aby se každý objevil před tím, na který ukazuje.

Tento algoritmus je aplikován na DAG (Directed Acyclic Graph), takže každý uzel se objeví v uspořádaném poli dříve, než na něj nasměrují všechny ostatní uzly. Tento algoritmus se opakovaně řídí některými pravidly, dokud není řazení dokončeno.

Pro zjednodušení se podívejte na následující příklad:

Zde můžeme vidět, že „A“ nemá žádný indegree. Znamená hranu, která ukazuje na uzel. „B“ a „C“ mají předpoklad „A“, potom „E“ má předpoklad uzlů „D“ a „F“. Některé z uzlů jsou závislé na jiných uzlech.

Zde je další znázornění výše uvedeného grafu:

Když tedy předáme DAG (Directed Acyclic Graph) topologickému řazení, dostaneme pole s lineárním uspořádáním, kde první prvek nemá žádnou závislost.

Tento příklad ukazuje graf s cyklem:

Postupujte takto:

Krok 1) Najděte uzel s nulovými vstupními hranami, uzel s nulovými stupni.

Krok 2) Uložte tento uzel na nulu do fronty nebo zásobníku a odeberte uzel z grafu.

Krok 3) Poté odstraňte odchozí hranu z tohoto uzlu.

Tím se sníží počet stupňů pro další uzel.

Topologické uspořádání vyžaduje, aby datová struktura grafu neměla žádný cyklus.

Graf bude považován za DAG, pokud splňuje tyto požadavky:

• Jeden nebo více uzlů s nestupňovou hodnotou nula.
• Graf neobsahuje žádný cyklus

Dokud jsou v grafu uzly a graf je stále DAG, provedeme výše uvedené tři kroky. Jinak algoritmus spadne do cyklické závislosti a Kahnův algoritmus nebude schopen najít uzel s nulovým stupněm.

Jak funguje topologické řazení

Zde použijeme pro topologické řazení „Kahnův algoritmus“. Řekněme, že máme následující graf:

Zde jsou kroky pro Kahnův algoritmus:

Krok 1) Vypočítejte nestupeň nebo vstupní hranu všech uzlů v grafu.

Poznámka:

• Indegree znamená nasměrované hrany směřující k uzlu.
• Outdegree znamená směrované hrany, které pocházejí z uzlu.

Zde je indegree a outdegree z výše uvedeného grafu:

Krok 2) Najděte uzel s nulovými stupni nebo nulovými vstupními hranami.

Uzel s nulovým stupněm znamená, že k tomuto uzlu nepřicházejí žádné hrany. Uzel „A“ má nulové stupně, což znamená, že žádná hrana neukazuje na uzel „A“.

Provedeme tedy následující akce:

• Odebrat tento uzel a jeho vnější okraje (odchozí okraje)
• Umístěte uzel do fronty pro objednání.
• Aktualizujte počet stupňů sousedního uzlu „A“.

Krok 3) Musíme najít uzel s indegrenální hodnotou nula. V tomto příkladu mají „B“ a „C“ nulový stupeň.

Zde si můžeme vzít jednu z těchto dvou. Vezmeme „B“ a odstraníme jej z grafu.

Potom aktualizujte nestupňové hodnoty ostatních uzlů.

Po provedení těchto operací bude náš graf a fronta vypadat následovně:

Krok 4) Uzel „C“ nemá žádnou vstupní hranu. Odebereme tedy uzel „C“ z grafu a vložíme jej do fronty.

Můžeme také odstranit hranu, která vychází z „C“.

Nyní bude náš graf vypadat takto:

Krok 5) Vidíme, že uzly „D“ a „F“ mají nulový stupeň. Vezmeme uzel a vložíme ho do fronty.

Nejprve vyjmeme „D“. Potom bude počet stupňů pro uzel „E“ 1. Nyní nebude žádný uzel od D do E.

Totéž musíme udělat pro uzel „F“, náš výsledek bude následující:

Krok 6) Indegree (vstupní hrany) a outdegre (odchozí hrany) uzlu „E“ se staly nulou. Splnili jsme tedy všechny předpoklady pro uzel „E“.

Zde jsme dali "E" na konec fronty. Takže nám nezbývají žádné uzly, takže algoritmus končí zde.

Pseudokód pro topologické třídění

Zde je pseudokód pro topologické řazení při použití Kahnova algoritmu.

function TopologicalSort( Graph G ):
  for each node in G:
    calculate the indegree
  start = Node with 0 indegree
  G.remove(start)
  topological_list = [start]
  While node with O indegree present:
    topological_list.append(node)
    G.remove(node)
    Update Indegree of present nodes
  Return topological_list

Topologické řazení lze také implementovat pomocí DFS (Hloubka první hledání) metoda. Tento přístup je však rekurzivní metodou. Kahnův algoritmus je efektivnější než přístup DFS.

C++ Implementace topologického třídění

#include<bits/stdc++.h>
using namespace std;
class graph{
  int vertices;
  list<int> *adjecentList;
public:
  graph(int vertices){
    this->vertices = vertices;
    adjecentList = new list<int>[vertices];
  }
  void createEdge(int u, int v){
    adjecentList[u].push_back(v);
  }
  void TopologicalSort(){
    // filling the vector with zero initially
    vector<int> indegree_count(vertices,0);

    for(int i=0;i<vertices;i++){
      list<int>::iterator itr;
      for(itr=adjecentList[i].begin(); itr!=adjecentList[i].end();itr++){
        indegree_count[*itr]++;
      }
    }
    queue<int> Q;
    for(int i=0; i<vertices;i++){
      if(indegree_count[i]==0){
        Q.push(i);
      }
    }
    int visited_node = 0;
    vector<int> order;
    while(!Q.empty()){
      int u = Q.front();
      Q.pop();
      order.push_back(u);

      list<int>::iterator itr;
      for(itr=adjecentList[u].begin(); itr!=adjecentList[u].end();itr++){
        if(--indegree_count[*itr]==0){
          Q.push(*itr);
        }
      }
      visited_node++;
    }
    if(visited_node!=vertices){
      cout<<"There's a cycle present in the Graph.\nGiven graph is not DAG"<<endl;
      return;
    }
    for(int i=0; i<order.size();i++){
      cout<<order[i]<<"\t";
    }
  }
};
int main(){
  graph G(6);
  G.createEdge(0,1);
  G.createEdge(0,2);
  G.createEdge(1,3);
  G.createEdge(1,5);
  G.createEdge(2,3);
  G.createEdge(2,5);
  G.createEdge(3,4);
  G.createEdge(5,4);
  G.TopologicalSort();
}

Výstup

0       1       2       3       5       4

Python Implementace topologického třídění

from collections import defaultdict
class graph:
    def __init__(self, vertices):
        self.adjacencyList = defaultdict(list) 
        self.Vertices = vertices  # No. of vertices
    # function to add an edge to adjacencyList
    def createEdge(self, u, v):
        self.adjacencyList[u].append(v)
    # The function to do Topological Sort.
    def topologicalSort(self):
        total_indegree = [0]*(self.Vertices)
        for i in self.adjacencyList:
            for j in self.adjacencyList[i]:
                total_indegree[j] += 1
        queue = []
        for i in range(self.Vertices):
            if total_indegree[i] == 0:
                queue.append(i)
        visited_node = 0
        order = []
        while queue:
            u = queue.pop(0)
            order.append(u)
            for i in self.adjacencyList[u]:
                total_indegree[i] -= 1

                if total_indegree[i] == 0:
                    queue.append(i)
            visited_node += 1
        if visited_node != self.Vertices:
            print("There's a cycle present in the Graph.\nGiven graph is not DAG")
        else:
            print(order)
G = graph(6)
G.createEdge(0,1)
G.createEdge(0,2)
G.createEdge(1,3)
G.createEdge(1,5)
G.createEdge(2,3)
G.createEdge(2,5)
G.createEdge(3,4)
G.createEdge(5,4)
G.topologicalSort()

Výstup

[0, 1, 2, 3, 5, 4]

Cyklické grafy topologického algoritmu řazení

Graf obsahující cyklus nelze topologicky seřadit. Protože cyklický graf má závislost cyklickým způsobem.

Podívejte se například na tento graf:

Tento graf není DAG (Directed Acyclic Graph), protože A, B a C vytvářejí cyklus. Pokud si všimnete, neexistuje žádný uzel s nulovou celostupňovou hodnotou.

Podle Kahnova algoritmu, pokud analyzujeme výše uvedený graf:

• Najděte uzel s nulovými stupni (žádné vstupní hrany).
• Odeberte tento uzel z grafu a vložte jej do fronty.
  Ve výše uvedeném grafu však není žádný uzel s nulou ve stupních. Každý uzel má hodnotu stupně větší než 0.
• Vraťte prázdnou frontu, protože nemohla najít žádný uzel s nulou ve stupních.

Cykly můžeme detekovat pomocí topologického uspořádání pomocí následujících kroků:

Krok 1) Proveďte topologické třídění.

Krok 2) Vypočítejte celkový počet prvků v topologicky seřazeném seznamu.

Krok 3) Pokud se počet prvků rovná celkovému počtu vrcholů, pak neexistuje žádný cyklus.

Krok 4) Pokud se nerovná počtu vrcholů, pak je v dané grafové datové struktuře alespoň jeden cyklus.

Analýza složitosti topologického řazení

V algoritmech existují dva typy složitosti. Jsou

1. Časová složitost
2. Složitost vesmíru

Tyto složitosti jsou reprezentovány funkcí, která poskytuje obecnou složitost.

Časová složitost: Veškerá časová složitost je stejná pro topologické třídění. Existují nejhorší, průměrné a nejlepší scénáře časové složitosti.

Časová složitost pro topologické řazení je O(E + V), zde E znamená počet hran v grafu a V znamená počet vrcholů v grafu.

Pojďme prolomit tuto složitost:

Krok 1) Na začátku spočítáme všechny stupně. Abychom to udělali, musíme projít všechny hrany a zpočátku přiřadíme všechny stupně V vrcholů nule. Takže postupné kroky, které dokončíme, budou O(V+E).

Krok 2) Najdeme uzel s nulovou indegren hodnotou. Musíme hledat z čísla V vrcholu. Dokončené kroky tedy budou O(V).

Krok 3) Pro každý uzel s nulovými stupni odstraníme tento uzel a snížíme stupeň. Provedení této operace pro všechny uzly bude trvat O(E).

Krok 4) Nakonec zkontrolujeme, zda existuje nějaký cyklus nebo ne. Zkontrolujeme, zda se celkový počet prvků v seřazeném poli rovná celkovému počtu uzlů. Zabere to O (1).

Jednalo se tedy o individuální časovou složitost pro každý krok topologického řazení nebo topologického uspořádání. Můžeme říci, že časová složitost z výše uvedeného výpočtu bude O( V + E ); zde O znamená funkci složitosti.

Prostorová složitost: Potřebovali jsme O(V) prostory pro spuštění topologického třídícího algoritmu.

Zde jsou kroky, kde jsme potřebovali prostor pro program:

• Museli jsme vypočítat všechny stupně uzlů přítomných v grafu. Vzhledem k tomu, že graf má celkem V uzlů, musíme vytvořit pole o velikosti V. Požadovaný prostor byl tedy O(V).
• K uložení uzlu s nulovým stupněm byla použita datová struktura Queue. Odstranili jsme uzly s nulovým stupněm z původního grafu a umístili je do fronty. K tomu byl potřebný prostor O(V).
• Pole se nazývá „objednávka“. To uložilo uzly v topologickém pořadí. To také vyžadovalo O(V) prostor.

Jednalo se o individuální prostorovou složitost. Musíme tedy tyto prostory za běhu maximalizovat.

Prostorová složitost znamená O(V), kde V znamená číslo vrcholu v grafu.

Aplikace topologického řazení

Topologické třídění má obrovské využití. Tady jsou některé z nich:

• Používá se, když Operating systému potřebuje provést alokaci zdrojů.
• Hledání cyklu v grafu. Můžeme ověřit, zda je graf DAG nebo ne, pomocí topologického řazení.
• Řazení vět v aplikacích automatického dokončování.
• Slouží k detekci uváznutí.
• Různé typy plánování nebo plánování kurzů používají topologické řazení.
• Řešení závislostí. Pokud se například pokusíte nainstalovat balíček, může tento balíček také potřebovat další balíčky. Topologické uspořádání zjistí všechny potřebné balíčky k instalaci aktuálního balíčku.
• Linux používá topologické řazení v „apt“ ke kontrole závislosti balíčků.