Topološki algoritam sortiranja: Python, C++ Primjer

Što je algoritam topološkog sortiranja?

Topološko sortiranje također je poznato kao Kahnov algoritam i popularan je algoritam sortiranja. Koristeći usmjereni graf kao ulaz, Topološko sortiranje razvrstava čvorove tako da se svaki pojavljuje ispred onog na koji pokazuje.

Ovaj algoritam se primjenjuje na DAG (usmjereni aciklički graf) tako da se svaki čvor pojavljuje u uređenom nizu prije svih ostalih čvorova na koje pokazuje. Ovaj algoritam ponavlja neka pravila dok se sortiranje ne završi.

Radi pojednostavljenja, pogledajte sljedeći primjer:

Usmjereni graf

Ovdje možemo vidjeti da "A" nema unutarnji stupanj. Unutarnji stupanj označava brid koji pokazuje na čvor. "B" i "C" imaju preduvjet "A", a "E" ima preduvjet čvorova "D" i "F". Neki od čvorova ovise o drugim čvorovima.

Evo još jednog prikaza gornjeg grafa:

Ovisnost svakog čvora (linearni poredak)

Dakle, kada proslijedimo DAG (usmjereni aciklički graf) topološkom sortiranju, to će nam dati niz s linearnim poretkom, gdje prvi element nema ovisnosti.

Evo koraka kako to učiniti:

Korak 1) Pronađite čvor s nula ulaznih rubova, čvor s nula stupnjeva.

Korak 2) Pohrani taj čvor s nultim stupnjem u red čekanja ili stog i ukloni čvor iz grafa.

Korak 3) Zatim izbrišite izlazni rub iz tog čvora. To će smanjiti broj unutarnjih stupnjeva za sljedeći čvor.

Topološko uređenje zahtijeva da struktura podataka grafa ne smije imati ciklus. Graf će se smatrati DAG-om ako ispunjava ove zahtjeve:

• Jedan ili više čvorova s ​​vrijednošću nestupnja nula.
• Graf ne sadrži nijedan ciklus.

Sve dok u grafu postoje čvorovi i graf je još uvijek DAG, izvršit ćemo gornja tri koraka. U suprotnom, algoritam će pasti u cikličku ovisnost i Kahnov algoritam neće moći pronaći čvor s nultim stupnjem ulaska.

Kako funkcionira topološko sortiranje

Ovdje ćemo koristiti „Kahnov algoritam“ za topološko sortiranje. Recimo da imamo sljedeći graf:

Evo koraka za Kahnov algoritam:

Korak 1) Izračunajte vanjski stupanj ili dolazni rub svih čvorova u grafu.

Bilješka:

• Indegree znači usmjerene bridove koji pokazuju na čvor.
• Outdegree znači usmjerene rubove koji dolaze iz čvora.

Evo stupnja unutar i izvan gornjeg grafa:

Korak 2) Pronađite čvor s nula unutarnjih stupnjeva ili nula dolaznih bridova. Čvor s nula unutarnjih stupnjeva znači da nikakvi bridovi ne dolaze prema tom čvoru. Čvor "A" ima nula unutarnjih stupnjeva, što znači da nema brida koji pokazuje na čvor "A". Dakle, učinit ćemo sljedeće radnje:

• Uklonite ovaj čvor i njegove rubove vanjskog stupnja (izlazne rubove).
• Stavite čvor u red čekanja za naručivanje.
• Ažurirajte broj stupnjeva susjednog čvora "A".

Korak 3) Moramo pronaći čvor s vrijednošću unutarnjeg stupnja nula. U ovom primjeru, "B" i "C" imaju nula unutarnjeg stupnja. Ovdje možemo uzeti bilo koji od ova dva. Uzmimo "B" i izbrišimo ga iz grafa. Zatim ažurirajmo vrijednosti unutarnjeg stupnja ostalih čvorova. Nakon izvođenja ovih operacija, naš graf i red čekanja izgledat će ovako:

Korak 4) Čvor "C" nema dolaznog brida. Dakle, uklonit ćemo čvor "C" iz grafa i staviti ga u red čekanja. Također možemo izbrisati brid koji izlazi iz "C". Sada će naš graf izgledati ovako:

Korak 5) Vidimo da čvorovi "D" i "F" imaju unutarnji stupanj nula. Uzet ćemo čvor i staviti ga u red čekanja. Prvo uklonimo "D". Tada će broj unutarnjih stupnjeva za čvor "E" biti 1. Sada neće biti čvora od D do E. Moramo učiniti isto za čvor "F" i naš rezultat će biti sljedeći:

Korak 6) Ulazni stupanj (ulazni bridovi) i izlazni stupanj (izlazni bridovi) čvora "E" postali su nula. Dakle, ispunili smo sve preduvjete za čvor "E". Ovdje ćemo staviti "E" na kraj reda čekanja. Dakle, nemamo više čvorova i algoritam ovdje završava.

Nadimak Code za topološko sortiranje

Evo pseudokoda za topološko sortiranje korištenjem Kahnovog algoritma.

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

Topološko sortiranje također se može implementirati pomoću DFS-a (Prvo pretraživanje dubine) metoda. Međutim, taj pristup je rekurzivna metoda. Kahnov algoritam je učinkovitiji od DFS pristupa.

C++ Implementacija topološkog sortiranja

#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();
}

Izlaz

0       1       2       3       5       4

Python Implementacija topološkog sortiranja

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

Izlaz

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

Ciklički grafovi algoritma topološkog sortiranja

Graf koji sadrži ciklus ne može biti topološki uređen, jer ciklički graf ima ovisnost na ciklički način. Na primjer, pogledajte ovaj graf:

Ovaj graf nije DAG (usmjereni aciklički graf) jer A, B i C stvaraju ciklus. Ako primijetite, ne postoji čvor s nultom vrijednošću stupnja ulaska. Prema Kahnovom algoritmu, ako analiziramo gornji graf:

• Pronađite čvor s nula indestupnjeva (bez dolazećih rubova).
• Uklonite taj čvor iz grafa i gurnite ga u red čekanja. Međutim, u gornjem grafu ne postoji čvor s nula stupnjeva u stupnju. Svaki čvor ima vrijednost stupnja u stupnju veću od 0.
• Vrati prazan red, jer nije mogao pronaći nijedan čvor s nula stupnjeva ulaska.

Možemo detektirati cikluse koristeći topološki poredak sa sljedećim koracima:

Korak 1) Izvršite topološko sortiranje.

Korak 2) Izračunajte ukupan broj elemenata u topološki sortiranoj listi.

Korak 3) Ako je broj elemenata jednak ukupnom broju vrhova, tada ne postoji ciklus.

Korak 4) Ako nije jednak broju vrhova, tada postoji barem jedan ciklus u danoj strukturi podataka grafa.

Analiza složenosti topološkog sortiranja

Postoje dvije vrste složenosti u algoritmima. To su:

1. Složenost vremena
2. Složenost prostora

Te su složenosti predstavljene funkcijom koja daje opću složenost.

Složenost vremena: Vremenska složenost je ista za topološko sortiranje. Postoje najgori, prosječni i najbolji scenariji vremenske složenosti. Vremenska složenost za topološko sortiranje je O(E + V), gdje E označava broj bridova u grafu, a V označava broj vrhova u grafu.

Probijmo se kroz ovu složenost:

Korak 1) Na početku ćemo izračunati sve stupnjeve. Da bismo to učinili, trebamo proći kroz sve bridove, a na početku ćemo dodijeliti sve stupnjeve V vrhova na nulu. Dakle, inkrementalni koraci koje dovršavamo bit će O(V+E).

Korak 2) Pronaći ćemo čvor s vrijednošću nultog stupnja. Trebamo tražiti od V broja vrha. Dakle, koraci će biti dovršeni O(V).

Korak 3) Za svaki čvor s nultim stupnjem, uklonit ćemo taj čvor i smanjiti indegrees. Izvođenje ove operacije za sve čvorove će potrajati O(E).

Korak 4) Na kraju ćemo provjeriti ima li ciklusa ili ne. Provjerit ćemo da li je ukupan broj elemenata u sortiranom nizu jednak ukupnom broju čvorova. Trebat će O (1).

Dakle, ovo su bile pojedinačne vremenske složenosti za svaki korak topološkog sortiranja ili topološkog uređenja. Možemo reći da će vremenska složenost iz gornjeg izračuna biti O(V + E); ovdje O označava funkciju složenosti.

Složenost prostora: Trebali smo O(V) prostora za pokretanje algoritma topološkog sortiranja. Evo koraka u kojima nam je bio potreban prostor za program:

• Morali smo izračunati sve stupnjeve čvorova prisutnih na grafikonu. Kako graf ima ukupno V čvorova, moramo stvoriti niz veličine V. Dakle, potreban prostor bio je O(V).
• Podatkovna struktura Queue korištena je za pohranjivanje čvora s nultim stupnjem. Uklonili smo čvorove s nultim stupnjem iz originalnog grafikona i smjestili ih u red čekanja. Za to je potreban prostor bio O(V).
• Niz se zove „order“ (redoslijed), koji pohranjuje čvorove u topološkom redoslijedu. To je također zahtijevalo O(V) mjesta.

To su bile pojedinačne prostorne složenosti. Dakle, moramo maksimizirati te prostore tijekom izvođenja. Prostorna složenost je kratica za O(V), gdje V označava broj vrha u grafu.

Primjena topološkog sortiranja

Topološko sortiranje ima ogromnu upotrebu. Evo nekih od njih:

• Koristi se kada Operating sustav treba izvršiti raspodjelu resursa.
• Pronalaženje ciklusa u grafu. Topološkim sortiranjem možemo provjeriti je li graf DAG ili ne.
• Redoslijed rečenica u aplikacijama za automatsko dovršavanje.
• Koristi se za otkrivanje zastoja.
• Različite vrste raspoređivanja ili raspoređivanja tečajeva koriste topološko sortiranje.
• Rješavanje ovisnosti. Na primjer, ako pokušate instalirati paket, taj paket može također trebati druge pakete. Topološki poredak pronalazi sve potrebne pakete za instalaciju trenutnog paketa.
• Linux koristi topološko sortiranje u "apt" za provjeru ovisnosti paketa.

Pitanja i odgovori