Topologický algoritmus řazení: Python, C++ Příklad

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 se aplikuje na DAG (Directed Acyclic Graph) tak, že každý uzel se v uspořádaném poli objeví před všemi ostatními uzly, na které ukazuje. Tento algoritmus opakovaně dodržuje určitá pravidla, dokud není řazení dokončeno.

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

Režírovaný graf

Zde vidíme, že „A“ nemá vnitřní stupeň. Vnitřní stupeň znamená hranu, která ukazuje na uzel. „B“ a „C“ mají předpoklad „A“, zatímco „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:

Závislost každého uzlu (lineární řazení)

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.

Zde jsou kroky, jak to provést:

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

Krok 2) Uložte tento uzel s nulovým stupněm vstupu do fronty nebo zásobníku a odeberte jej z grafu.

Krok 3) Pak odstraňte odchozí hranu z daného uzlu. Tím se sníží počet vstupních stupňů pro další uzel.

Topologické uspořádání vyžaduje, aby datová struktura grafu neobsahovala žá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 vnějšího gradientu.

Jak funguje topologické řazení

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

Zde jsou kroky pro Kahnova algoritmu:

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 vnitřní a vnější stupeň výše uvedeného grafu:

Krok 2) Najděte uzel s nulovým stupněm inputu nebo nulovou hranou směřující do něj. Uzel s nulovým stupněm inputu znamená, že k tomuto uzlu nepřicházejí žádné hrany. Uzel „A“ má nulový stupeň inputu, což znamená, že žádná hrana nesměřuje do uzlu „A“. Provedeme tedy následující akce:

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

Krok 3) Potřebujeme najít uzel s nulovým indegree. V tomto příkladu mají uzly „B“ a „C“ nulový indegree. Zde můžeme vzít kterýkoli z těchto dvou. Vezměme „B“ a smažme ho z grafu. Poté aktualizujme hodnoty indegree ostatních uzlů. Po provedení těchto operací bude náš graf a fronta vypadat následovně:

Krok 4) Uzel „C“ nemá žádnou vstupní hranu. Takže uzel „C“ z grafu odstraníme a vložíme ho do fronty. Můžeme také smazat hranu, která z „C“ vychází. Náš graf bude nyní vypadat takto:

Krok 5) Vidíme, že uzly „D“ a „F“ mají nulový vstupní stupeň. Vezmeme jeden uzel a vložíme ho do fronty. Nejprve odebereme „D“. Počet vstupních stupňů pro uzel „E“ bude 1. Nyní nebude žádný uzel z D do E. Totéž musíme udělat pro uzel „F“ a náš výsledek bude vypadat takto:

Krok 6) Vstupní stupeň (vstupní hrany) a výstupní stupeň (výstupní hrany) uzlu „E“ se stal nulovým. Splnili jsme tedy všechny předpoklady pro uzel „E“. Zde umístíme „E“ na konec fronty. Takže nám nezbývají žádné uzly a algoritmus zde končí.

Nepravý Code pro topologické třídění

Zde je pseudokód pro topologické třídění s využitím 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 0 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 uspořádat, 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 hodnotou vnitřního stupně. Podle Kahnova algoritmu, pokud analyzujeme výše uvedený graf:

• Najděte uzel s nulovými stupni (žádné vstupní hrany).
• Odeberte daný uzel z grafu a vložte ho do fronty. Ve výše uvedeném grafu však není žádný uzel s nulovou hodnotou stupňů. Každý uzel má hodnotu stupně větší než 0.
• Vrátí prázdnou frontu, protože nenajde žádný uzel s nulovými stupni.

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 v dané datové struktuře grafu existuje alespoň jeden cyklus.

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

V algoritmech existují dva typy složitosti. Jsou to:

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

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

Časová složitost: Časová složitost topologického třídění je veškerá stejná. Existují nejhorší, průměrný a nejlepší scénáře časové složitosti. Časová složitost topologického třídění je O(E + V), kde E znamená počet hran v grafu a V znamená počet vrcholů v grafu.

Pojďme se s touto složitostí vypořádat:

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).

Takže to byly jednotlivé časové složitosti pro každý krok topologického třídění 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: Pro spuštění algoritmu topologického třídění jsme potřebovali O(V) prostorů. Zde jsou kroky, ve kterých jsme tento prostor pro program potřebovali:

• 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 s názvem „order“ (pořadí) ukládá uzly v topologickém pořadí. To také vyžadovalo O(V) prostor.

Toto byly jednotlivé prostorové složitosti. Takže musíme tyto prostory maximalizovat za běhu programu. Prostorová složitost je zkratka pro O(V), kde V znamená číslo vrcholu v grafu.

Aplikace topologického řazení

Topologické třídění má obrovské využití. Zde je několik z nich:

• Používá se, když Operating systému potřebuje provést alokaci zdrojů.
• Nalezení cyklu v grafu. Topologickým tříděním můžeme ověřit, zda je graf DAG či nikoli.
• Řazení vět v aplikacích automatického dokončování.
• Používá se 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ů.

Nejčastější dotazy