Sortare topologică: Python, C++ Exemplu de algoritm

Ce este algoritmul de sortare topologică?

Sortarea topologică este cunoscută și ca algoritmul lui Kahn și este un algoritm de sortare popular. Folosind un grafic direcționat ca intrare, Sortarea topologică sortează nodurile astfel încât fiecare să apară înaintea celui către care indică.

Acest algoritm este aplicat pe un DAG (Grafic aciclic direcționat) astfel încât fiecare nod să apară în matricea ordonată înainte ca toate celelalte noduri să fie îndreptate către el. Acest algoritm urmează câteva reguli în mod repetat până când sortarea este finalizată.

Pentru a simplifica, uitați-vă la următorul exemplu:

Aici, putem vedea că „A” nu are indegree. Înseamnă marginea care indică un nod. „B” și „C” au o condiție prealabilă de „A”, apoi „E” are o condiție prealabilă a nodurilor „D” și „F”. Unele dintre noduri depind de alte noduri.

Iată o altă reprezentare a graficului de mai sus:

Deci, când trecem DAG (Graficul aciclic direcționat) la sortarea topologică, ne va oferi o matrice cu ordonare liniară, în care primul element nu are nicio dependență.

Acest exemplu arată un grafic cu un ciclu:

Iată pașii pentru a face acest lucru:

Pas 1) Găsiți nodul cu zero margini de intrare, un nod cu zero grade.

Pas 2) Stocați care pune la zero nodul în grad într-o coadă sau stivă și elimină nodul din grafic.

Pas 3) Apoi ștergeți marginea de ieșire din acel nod.

Acest lucru va reduce numărul de grade pentru următorul nod.

Ordonarea topologică necesită ca structura de date a graficului să nu aibă niciun ciclu.

Un grafic va fi considerat un DAG dacă respectă aceste cerințe:

• Unul sau mai multe noduri cu o valoare de grad zero.
• Graficul nu conține niciun ciclu

Atâta timp cât există noduri în Graph și Graph-ul este încă DAG, vom rula cei trei pași de mai sus. În caz contrar, algoritmul va cădea în dependența ciclică, iar algoritmul lui Kahn nu va putea găsi un nod cu zero în grad.

Cum funcționează sortarea topologică

Aici, vom folosi „Algoritmul lui Kahn” pentru sortarea topologică. Să presupunem că avem următorul grafic:

Iată pașii pentru algoritmul lui Kahn:

Pas 1) Calculați gradul sau marginea de intrare a tuturor nodurilor din grafic.

Notă:

• Indegree înseamnă marginile direcționate îndreptate către nod.
• Outdegree înseamnă marginile direcționate care provin dintr-un nod.

Iată gradul și gradul exterior al graficului de mai sus:

Pas 2) Găsiți nodul cu zero grade sau zero margini de intrare.

Nodul cu zero grade înseamnă că nicio margine nu vine spre acel nod. Nodul „A” are zero grade, ceea ce înseamnă că nu există nicio margine îndreptată către nodul „A”.

Deci, vom face următoarele acțiuni:

• Eliminați acest nod și marginile sale exterioare (marginile de ieșire)
• Plasați nodul în coadă pentru comandă.
• Actualizați numărul în grade al nodului vecin de „A”.

Pas 3) Trebuie să găsim un nod cu o valoare de grad zero. În acest exemplu, „B” și „C” au grade zero.

Aici, putem lua oricare dintre aceste două. Să luăm „B” și să-l ștergem din grafic.

Apoi actualizați valorile indegree ale altor noduri.

După efectuarea acestor operații, graficul și coada noastră vor arăta astfel:

Pas 4) Nodul „C” nu are margine de intrare. Deci, vom elimina nodul „C” din grafic și îl vom împinge în coadă.

De asemenea, putem șterge marginea care iese din „C”.

Acum, graficul nostru va arăta astfel:

Pas 5) Putem vedea că nodurile „D” și „F” au gradul zero. Vom lua un nod și îl vom pune în coadă.

Să scoatem mai întâi „D”. Apoi, numărul de grade pentru nodul „E” va fi 1. Acum, nu va exista niciun nod de la D la E.

Trebuie să facem același lucru pentru nodul „F”, rezultatul nostru va fi următorul:

Pas 6) Indegree (muchiile de intrare) și gradul de exterior (muchiile de ieșire) ale nodului „E” au devenit zero. Deci, am îndeplinit toate condițiile prealabile pentru nodul „E”.

Aici, am pus „E” la sfârșitul Cozii. Deci, nu mai avem niciun nod, așa că algoritmul se termină aici.

Pseudocod pentru sortarea topologică

Iată pseudo-codul pentru sortarea topologică în timp ce utilizați algoritmul lui Kahn.

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

Sortarea topologică poate fi implementată și folosind DFS (Căutare în adâncime) metoda. Cu toate acestea, această abordare este metoda recursivă. Algoritmul lui Kahn este mai eficient decât abordarea DFS.

C++ Implementarea sortării topologice

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

producție

0       1       2       3       5       4

Python Implementarea sortării topologice

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

producție

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

Grafice ciclice ale algoritmului de sortare topologică

Un grafic care conține un ciclu nu poate fi ordonat topologic. Deoarece graficul ciclic are dependența într-o manieră ciclică.

De exemplu, verificați acest grafic:

Acest grafic nu este DAG (Grafic aciclic direcționat) deoarece A, B și C creează un ciclu. Dacă observați, nu există niciun nod cu valoare zero în grad.

Conform algoritmului lui Kahn, dacă analizăm graficul de mai sus:

• Găsiți un nod cu zero grade (fără margini de intrare).
• Scoateți acel nod din grafic și împingeți-l în coadă.
  Cu toate acestea, în graficul de mai sus, nu există niciun nod cu zero în grade. Fiecare nod are o valoare în grad mai mare decât 0.
• Returnează o coadă goală, deoarece nu a putut găsi niciun nod cu zero în grade.

Putem detecta ciclurile folosind ordinea topologică cu următorii pași:

Pas 1) Efectuați sortarea topologică.

Pas 2) Calculați numărul total de elemente din lista sortată topologic.

Pas 3) Dacă numărul de elemente este egal cu numărul total de vârfuri, atunci nu există ciclu.

Pas 4) Dacă nu este egal cu numărul de vârfuri, atunci există cel puțin un ciclu în structura de date a graficului dată.

Analiza complexității sortării topologice

Există două tipuri de complexitate în algoritmi. Ei sunt

1. Complexitatea timpului
2. Complexitatea spațială

Aceste complexități sunt reprezentate cu o funcție care oferă o complexitate generală.

Complexitatea timpului: Complexitatea timpului este aceeași pentru Sortarea topologică. Există scenarii cele mai rele, medii și cele mai bune pentru complexitatea timpului.

Complexitatea timpului pentru sortarea topologică este O(E + V), aici, E înseamnă numărul de Muchii din Grafic și V înseamnă numărul de vârfuri din Grafic.

Să trecem prin această complexitate:

Pas 1) La început, vom calcula toate gradele. Pentru a face acest lucru, trebuie să trecem prin toate muchiile și, inițial, vom atribui toate V indexurile de vârf la zero. Deci, pașii incrementali pe care îi parcurgem vor fi O(V+E).

Pas 2) Vom găsi nodul cu valoare de grade zero. Trebuie să căutăm din numărul V al vârfului. Deci, pașii parcurși vor fi O(V).

Pas 3) Pentru fiecare nod cu zero grade, vom elimina acel nod și vom decrementa indicele. Efectuarea acestei operații pentru toate nodurile va dura O(E).

Pas 4) În cele din urmă, vom verifica dacă există sau nu vreun ciclu. Vom verifica dacă numărul total de elemente din tabloul sortat este egal cu numărul total de noduri. Va dura O (1).

Deci, acestea au fost complexitatea de timp individuală pentru fiecare pas al Sortării topologice sau ordonării topologice. Putem spune că complexitatea timpului din calculul de mai sus va fi O( V + E ); aici, O înseamnă funcția de complexitate.

Complexitatea spațială: Aveam nevoie de spații O(V) pentru rularea algoritmului de sortare topologică.

Iată pașii în care am avut nevoie de spațiu pentru program:

• A trebuit să calculăm toate gradele nodurilor prezente în grafic. Deoarece Graficul are un total de V noduri, trebuie să creăm o matrice de dimensiunea V. Deci, spațiul necesar a fost O(V).
• A fost folosită o structură de date coadă pentru a stoca nodul cu zero grade. Am eliminat nodurile cu zero indegree din graficul original și le-am plasat în coadă. Pentru aceasta, spațiul necesar a fost O(V).
• Matricea se numește „comandă”. Asta a stocat nodurile în ordine topologică. A fost nevoie și de asta O(V) spații.

Acestea au fost complexitatea spațiului individual. Deci, trebuie să maximizăm aceste spații în timpul de rulare.

Complexitatea spațiului reprezintă O(V), unde V înseamnă numărul vârfurilor din grafic.

Aplicarea sortării topologice

Există o utilizare uriașă pentru sortarea topologică. Aici sunt câțiva dintre ei:

• Se foloseste cand Operasistem de ting trebuie să efectueze alocarea resurselor.
• Găsirea unui ciclu în grafic. Putem valida dacă Graficul este DAG sau nu cu sortare topologică.
• Ordonarea propozițiilor în aplicațiile de completare automată.
• Este folosit pentru a detecta blocaje.
• Diferite tipuri de programare sau programare de curs utilizează sortarea topologică.
• Rezolvarea dependențelor. De exemplu, dacă încercați să instalați un pachet, acel pachet ar putea avea nevoie și de alte pachete. Ordonarea topologică descoperă toate pachetele necesare pentru a instala pachetul curent.
• Linux folosește sortarea topologică în „apt” pentru a verifica dependența pachetelor.