Topološko sortiranje: Python, C++ Primjer algoritma
Sarah Chen
Š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 se algoritam primjenjuje na DAG (usmjereni aciklički graf) tako da se svaki čvor pojavljuje u uređenom nizu prije nego što svi drugi čvorovi usmjere na njega. Ovaj algoritam opetovano slijedi neka pravila dok se sortiranje ne završi.
Radi pojednostavljenja, pogledajte sljedeći primjer:
Ovdje možemo vidjeti da "A" nema stupanj. To znači rub koji pokazuje na čvor. “B” i “C” imaju preduvjet “A”, zatim “E” ima preduvjet čvorove “D” i “F”. Neki od čvorova ovise o drugim čvorovima.
Evo još jednog prikaza gornjeg grafikona:
Dakle, kada proslijedimo DAG (usmjereni aciklički graf) topološkom sortiranju, to će nam dati niz s linearnim poretkom, gdje prvi element nema ovisnosti.
Ovaj primjer prikazuje grafikon s ciklusom:
Evo koraka za to:
Korak 1) Pronađite čvor s nula ulaznih rubova, čvor s nula stupnjeva.
Korak 2) Pohranite taj čvor nultog stupnja u red čekanja ili hrpu i uklonite čvor s grafikona.
Korak 3) Zatim izbrišite izlazni rub iz tog čvora.
Ovo će smanjiti broj stupnjeva za sljedeći čvor.
Topološko uređenje zahtijeva da struktura podataka grafa nema nikakav 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 postoje čvorovi u Graphu i Graph je još uvijek DAG, pokrenut ćemo gornja tri koraka. U suprotnom, algoritam će pasti u cikličku ovisnost, a Kahnov algoritam neće moći pronaći čvor s nultim in-stupnjem.
Kako funkcionira topološko sortiranje
Ovdje ćemo koristiti “Kahnov algoritam” za topološko sortiranje. Recimo da imamo sljedeći grafikon:
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 i smjera gornjeg grafikona:
Korak 2) Pronađite čvor s nula indestupnjeva ili nula ulaznih rubova.
Čvor s nultim stupnjem znači da rubovi ne dolaze prema tom čvoru. Čvor “A” ima nula stupnjeva, što znači da nema ruba koji pokazuje na čvor “A”.
Dakle, izvršit ćemo sljedeće radnje:
- Uklonite ovaj čvor i njegove vanjske rubove (odlazni rubovi)
- Stavite čvor u red čekanja za naručivanje.
- Ažurirajte broj stupnjeva susjednog čvora "A."
Korak 3) Moramo pronaći čvor s vrijednošću nestupnja nula. U ovom primjeru, "B" i "C" imaju nulti stupanj.
Ovdje možemo uzeti bilo koje od ovo dvoje. Uzmimo "B" i izbrišemo ga s grafikona.
Zatim ažurirajte vrijednosti stupnja drugih čvorova.
Nakon izvođenja ovih operacija, naš grafikon i red čekanja izgledat će ovako:
Korak 4) Čvor “C” nema dolazni rub. Dakle, uklonit ćemo čvor "C" s Grafa i gurnuti ga u red čekanja.
Također možemo izbrisati rub koji izlazi iz "C".
Sada će naš grafikon izgledati ovako:
Korak 5) Možemo vidjeti da čvorovi "D" i "F" imaju indegres nule. Uzet ćemo čvor i staviti ga u red čekanja.
Prvo izbacimo "D". Tada će broj stupnjevanja za čvor "E" biti 1. Sada, neće biti čvora od D do E.
Moramo učiniti isto za čvor "F", naš rezultat će biti sljedeći:
Korak 6) Indegree (ulazni rubovi) i outdegree (odlazni bridovi) čvora "E" postali su nula. Dakle, ispunili smo sve preduvjete za čvor “E”.
Ovdje stavljamo "E" na kraj reda čekanja. Dakle, nemamo više čvorova, tako da algoritam ovdje završava.
Pseudo kod za topološko sortiranje
Evo pseudokoda za topološko sortiranje pri korištenju Kahnova 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 O 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. Kako ciklički graf ima ovisnost na ciklički način.
Na primjer, provjerite ovaj grafikon:
Ovaj graf nije DAG (usmjereni aciklički graf) jer A, B i C stvaraju ciklus. Ako primijetite, nema čvora s nultom vrijednošću stupnja.
Prema Kahnovom algoritmu, ako analiziramo gornji grafikon:
- Pronađite čvor s nula indestupnjeva (bez dolazećih rubova).
- Uklonite taj čvor s grafikona i gurnite ga u red čekanja.
Međutim, na gornjem grafikonu ne postoji čvor s nulom u stupnjevima. Svaki čvor ima vrijednost u stupnju veću od 0. - Vrati prazan red jer nije mogao pronaći nijedan čvor s nulom u stupnjevima.
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 nema ciklusa.
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 algoritama. oni su
- Složenost vremena
- Složenost prostora
Te su složenosti predstavljene funkcijom koja daje opću složenost.
Složenost vremena: Sva vremenska složenost je ista za topološko sortiranje. Postoje najgori, prosječni i najbolji scenariji za vremensku složenost.
Vremenska složenost za topološko sortiranje je O(E + V), ovdje E označava broj rubova 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, to je bila individualna vremenska složenost za svaki korak topološkog sortiranja ili topološkog sređivanja. Možemo reći da će vremenska složenost iz gornjeg izračuna biti O( V + E ); ovdje O znači funkciju složenosti.
Složenost prostora: Trebali smo O(V) prostore za izvođenje algoritma topološkog sortiranja.
Evo koraka u kojima nam je trebao 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 "red". To je pohranilo čvorove u topološkom redu. To je također zahtijevalo O(V) mjesta.
To su bile individualne složenosti prostora. Dakle, moramo maksimizirati ove prostore u vremenu izvođenja.
Prostorna složenost označava O(V), gdje V označava broj vrhova u grafu.
Primjena topološkog sortiranja
Postoji ogromna upotreba topološkog sortiranja. Ovo su neki 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 nije.
- Redoslijed rečenica u aplikacijama za automatsko dovršavanje.
- Koristi se za otkrivanje zastoja.
- Različite vrste rasporeda ili rasporeda 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.
