Algoritmul de sortare topologică: Python, C++ Exemplu

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 (Graf Aciclic Direcționat) astfel încât fiecare nod să apară în matricea ordonată înaintea tuturor celorlalte noduri la care indică. Acest algoritm urmează în mod repetat anumite reguli până când sortarea este finalizată.

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

Graficul Dirijat

Aici, putem vedea că „A” nu are grad intern. Gradul intern reprezintă muchia care indică un nod. „B” și „C” au o precondiție de „A”, apoi „E” are o precondiție de noduri „D” și „F”. Unele dintre noduri sunt dependente de alte noduri.

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

Dependența fiecărui nod (ordonare liniară)

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ță.

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 acel nod cu gradul zero într-o coadă sau o stivă și eliminați nodul din grafic.

Pas 3) Apoi ștergeți muchia de ieșire din acel nod. Aceasta va reduce numărul de grade în interior pentru următorul nod.

Ordonarea topologică impune ca structura de date a grafului să nu aibă niciun ciclu. Un graf va fi considerat un DAG dacă îndeplinește 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 Graf și Graful este încă un 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 grad zero.

Cum funcționează sortarea topologică

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

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 interior și gradul exterior ale graficului de mai sus:

Pas 2) Găsiți nodul cu zero grade de intrare sau zero muchii de intrare. Nodul cu zero grade de intrare înseamnă că nicio muchie nu se îndreaptă spre acel nod. Nodul „A” are zero grade de intrare, ceea ce înseamnă că nu există nicio muchie care să indice spre nodul „A”. Așadar, vom face următoarele acțiuni:

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

Pas 3) Trebuie să găsim un nod cu o valoare a gradului interior zero. În acest exemplu, „B” și „C” au gradul interior zero. Aici, putem lua oricare dintre aceste două. Să luăm „B” și să-l ștergem din Grafic. Apoi actualizăm valorile gradului interior ale celorlalte noduri. După efectuarea acestor operațiuni, Graficul și Coada noastră vor arăta astfel:

Pas 4) Nodul „C” nu are o muchie de intrare. Așadar, vom elimina nodul „C” din Graf și îl vom introduce în coadă. De asemenea, putem șterge muchia de ieșire din „C”. Acum, Graficul nostru va arăta astfel:

Pas 5) Putem vedea că nodurile „D” și „F” au gradul interior zero. Vom lua un nod și îl vom pune în coadă. Să eliminăm mai întâi „D”. Apoi, numărul de grade interior 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”, iar rezultatul nostru va fi următorul:

Pas 6) Gradul interior (muchiile de intrare) și gradul exterior (muchiile de ieșire) ale nodului „E” au devenit zero. Deci, am îndeplinit toate cerințele preliminare pentru nodul „E”. Aici, vom pune „E” la sfârșitul cozii. Deci, nu ne-au mai rămas noduri, iar algoritmul se termină aici.

Pseudo Code pentru sortare topologică

Iată pseudo-codul pentru sortarea topologică folosind 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 0 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 graf care conține un ciclu nu poate fi ordonat topologic, deoarece graful ciclic are dependența într-o manieră ciclică. De exemplu, verificați acest graf:

Acest graf nu este un DAG (graf 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 graful de mai sus:

• Găsiți un nod cu zero grade (fără margini de intrare).
• Eliminați acel nod din Grafic și mutați-l în Coadă. Totuși, în Graficul de mai sus, nu există niciun nod cu zero grade în interior. Fiecare nod are o valoare a gradelor în interior mai mare decât 0.
• Returnează o coadă goală, deoarece nu a putut găsi niciun nod cu zero grade în interior.

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 grafului dată.

Analiza complexității sortării topologice

Există două tipuri de complexitate în algoritmi. Acestea 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 temporală este aceeași pentru sortarea topologică. Există scenarii negative, medii și pozitive pentru complexitatea temporală. Complexitatea temporală pentru sortarea topologică este O(E + V), unde E reprezintă numărul de muchii din graf, iar V reprezintă numărul de vârfuri din graf.

Să depășim 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 complexitățile temporale individuale pentru fiecare pas al sortării topologice sau al ordonării topologice. Putem spune că complexitatea temporală din calculul de mai sus va fi O(V + E); aici, O reprezintă 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țiul 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).
• Tabloul este denumit „order”, care a stocat nodurile în ordine topologică. Aceasta a necesitat, de asemenea, O(V) spații.

Acestea au fost complexitățile spațiale individuale. Așadar, trebuie să maximizăm aceste spații în timpul execuției. Complexitatea spațială reprezintă O(V), unde V reprezintă numărul vârfurilor din graf.

Aplicarea sortării topologice

Sortarea topologică are o utilizare enormă. Iată câteva dintre ele:

• Se folosește atunci când un Operasistem de ting trebuie să efectueze alocarea resurselor.
• Găsirea unui ciclu în graf. Putem valida dacă graful este un DAG sau nu cu sortare topologică.
• Ordonarea propozițiilor în aplicațiile de completare automată.
• Se folosește pentru detectarea blocaje.
• Diferite tipuri de planificare sau planificare a cursurilor 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.

Întrebări frecvente