logo

TechCodeview

Ordenació topològica

Ordenació topològica per Gràfic acíclic dirigit (DAG) és una ordenació lineal de vèrtexs tal que per a cada aresta dirigida u-v, vèrtex en ve abans en en l'ordenació.

Nota: L'ordenació topològica d'un gràfic no és possible si el gràfic no és a DIA .



Exemple:

Entrada: Gràfic :

números de l'alfabet
exemple

Exemple



Sortida: 5 4 2 3 1 0
Explicació: El primer vèrtex en l'ordenació topològica és sempre un vèrtex amb un grau d'entrada de 0 (un vèrtex sense arestes entrants). Una ordenació topològica del gràfic següent és 5 4 2 3 1 0. Pot haver-hi més d'una ordenació topològica per a un gràfic. Una altra ordenació topològica del gràfic següent és 4 5 2 3 1 0.

Pràctica recomanadaSolució basada en DFS per trobar una classificació topològica ja s'ha parlat.

L'ordre topològic pot no ser únic:

Ordenació topològica és un problema de dependència en què la realització d'una tasca depèn de la realització d'altres tasques l'ordre de les quals pot variar. Entenem aquest concepte amb un exemple:



Suposem que la nostra tasca és arribar a la nostra Escola i per arribar-hi, primer ens hem de vestir. Les dependències per portar roba es mostren al gràfic de dependències següent. Per exemple, no pots portar sabates abans de posar-te mitjons.

1

A partir de la imatge de dalt, ja hauríeu adonat que existeixen múltiples maneres de vestir-vos, la imatge de sota mostra algunes d'aquestes maneres.

2

Pots enumerar tot l'ordenament topològic possible de vestir-se per al gràfic de dependència anterior?

Algorisme per a l'ordenació topològica mitjançant DFS:

A continuació, es mostra un algorisme pas a pas per a l'ordenació topològica mitjançant Depth First Search (DFS):

  • Crea un gràfic amb n vèrtexs i m - vores dirigides.
  • Inicialitzar una pila i una matriu de mida visitada n .
  • Per a cada vèrtex no visitat del gràfic, feu el següent:
    • Truqueu a la funció DFS amb el vèrtex com a paràmetre.
    • A la funció DFS, marqueu el vèrtex com a visitat i truqueu recursivament a la funció DFS per a tots els veïns no visitats del vèrtex.
    • Un cop visitats tots els veïns, empènyer el vèrtex a la pila.
  • Després de tot, s'han visitat els vèrtexs, extreu elements de la pila i afegiu-los a la llista de sortida fins que la pila estigui buida.
  • La llista resultant és l'ordre topològicament ordenat del gràfic.

Il·lustració Algorisme d'ordenació topològica:

La imatge següent és una il·lustració de l'enfocament anterior:

Ordenació topològica

Flux de treball global de l'ordenació topològica

Pas 1:

  • Iniciem DFS des del node 0 perquè té zero nodes entrants
  • Empengem el node 0 a la pila i passem al següent node amb un nombre mínim de nodes adjacents, és a dir, el node 1.

dossier

Pas 2:

  • En aquest pas, com que no hi ha cap adjacent d'aquest node, premeu el node 1 a la pila i aneu al següent node.

dossier

Pas 3:

  • En aquest pas, escollim el node 2 perquè té un nombre mínim de nodes adjacents després de 0 i 1.
  • Anomenem DFS per al node 2 i empenyem tots els nodes que es recorren des del node 2 en ordre invers.
  • Així que premeu 3 i després premeu 2.

dossier

Pas 4:

  • Ara anomenem DFS per al node 4
  • Com que el 0 i l'1 ja estan presents a la pila, només hem d'empènyer el node 4 a la pila i tornar.

dossier

Pas 5:

  • En aquest pas, perquè tots els nodes adjacents de 5 ja estan a la pila, empenyem el node 5 a la pila i tornem.

dossier

llista d'enllaços en java

Pas 6: Aquest és l'últim pas de l'ordenació topològica en la qual extraïm tot l'element de la pila i l'imprimim en aquest ordre.

A continuació es mostra la implementació de l'enfocament anterior:

C++ 
#include  using namespace std; // Function to perform DFS and topological sorting void topologicalSortUtil(int v, vector>& adj, vector & visitat, apilar & Stack) { // Marca el node actual com a visitat visitat[v] = true;  // Es repeteix per a tots els vèrtexs adjacents per a (int i : adj[v]) { if (!visited[i]) topologicalSortUtil(i, adj, visited, Stack);  } // Empènyer el vèrtex actual a la pila que emmagatzema el resultat Stack.push(v); } // Funció per realitzar l'ordenació topològica void topologicalSort (vector>& adj, int V) { pila pila; // Apilar per emmagatzemar el vector resultat visitat(V, fals);  // Crida la funció d'ajuda recursiva per emmagatzemar // Ordenació topològica començant per tots els vèrtexs un per // un per (int i = 0; i< V; i++) {  if (!visited[i])  topologicalSortUtil(i, adj, visited, Stack);  }  // Print contents of stack  while (!Stack.empty()) {  cout << Stack.top() << ' ';  Stack.pop();  } } int main() {  // Number of nodes  int V = 4;  // Edges  vector> vores = { { 0, 1 }, { 1, 2 }, { 3, 1 }, { 3, 2 } };  // Gràfic representat com un vector de llista d'adjacència> adj(V);  per (auto i: vores) { adj[i[0]].push_back(i[1]);  } cout<< 'Topological sorting of the graph: ';  topologicalSort(adj, V);  return 0; }>
Java 
import java.util.*; public class TopologicalSort {  // Function to perform DFS and topological sorting  static void  topologicalSortUtil(int v, List> adj, booleà[] visitat, Stack stack) { // Marca el node actual com a visitat visitat[v] = true;  // Es repeteix per a tots els vèrtexs adjacents per a (int i : adj.get(v)) { if (!visited[i]) topologicalSortUtil(i, adj, visited, stack);  } // Empènyer el vèrtex actual a la pila que emmagatzema el // resultat stack.push(v);  } // Funció per realitzar l'ordenació topològica static void topologicalSort(Lista> adj, int V) { // Stack per emmagatzemar el resultat Stack pila = nova pila ();  booleà[] visitat = booleà nou[V];  // Crida la funció d'ajuda recursiva per emmagatzemar // Ordenació topològica començant per tots els vèrtexs un // per un per (int i = 0; i< V; i++) {  if (!visited[i])  topologicalSortUtil(i, adj, visited, stack);  }  // Print contents of stack  System.out.print(  'Topological sorting of the graph: ');  while (!stack.empty()) {  System.out.print(stack.pop() + ' ');  }  }  // Driver code  public static void main(String[] args)  {  // Number of nodes  int V = 4;  // Edges  List> vores = new ArrayList();  edges.add(Matrius.asList(0, 1));  edges.add(Matrius.asList(1, 2));  edges.add(Matrius.asList(3, 1));  edges.add(Matrius.asList(3, 2));  // Gràfic representat com una llista d'adjacència> adj = new ArrayList (V);  per (int i = 0; i< V; i++) {  adj.add(new ArrayList());  }  for (List i : vores) { adj.get(i.get(0)).add(i.get(1));  } TopologicalSort(adj, V);  } }>>>Python 3
C# 
using System; using System.Collections.Generic; class Program {  // Function to perform DFS and topological sorting  static void TopologicalSortUtil(int v,  List> adj, bool[] visitat, Stack stack) { // Marca el node actual com a visitat visitat[v] = true;  // Es repeteix per a tots els vèrtexs adjacents foreach(int i in adj[v]) { if (!visited[i]) TopologicalSortUtil(i, adj, visited, stack);  } // Empènyer el vèrtex actual a la pila que emmagatzema // la pila de resultats. Push(v);  } // Funció per realitzar l'ordenació topològica static void TopologicalSort(Lista> adj, int V) { // Stack per emmagatzemar el resultat Stack pila = pila nova ();  bool[] visitat = bool[V] nou;  // Crida la funció d'ajuda recursiva per emmagatzemar // Ordenació topològica començant per tots els vèrtexs un // per un per (int i = 0; i< V; i++) {  if (!visited[i])  TopologicalSortUtil(i, adj, visited, stack);  }  // Print contents of stack  Console.Write('Topological sorting of the graph: ');  while (stack.Count>0) { Console.Write(stack.Pop() + ' ');  } } // Codi del controlador static void Main(string[] args) { // Nombre de nodes int V = 4;  // Llista de vores> vores = nova llista>{ nova llista {0, 1}, llista nova {1, 2}, llista nova { 3, 1 }, llista nova { 3, 2 } };  // Gràfic representat com a llista d'adjacència> adj = llista nova>();  per (int i = 0; i< V; i++) {  adj.Add(new List ());  } foreach(Llista i a les vores) { adj[i[0]].Afegir(i[1]);  } TopologicalSort(adj, V);  } }>>>Javascript0) { console.log(stack.pop() + ' ');  } } // Codi del controlador (() => { // Nombre de nodes const V = 4; // Vores const arestes = [[0, 1], [1, 2], [3, 1], [3, 2]]; // Gràfic representat com una llista d'adjacència const adj = Array.from({longitud: V }, () => []); (i[1]);>>>  
  Sortida  
Topological sorting of the graph: 3 0 1 2>
  
    Complexitat temporal:    O(V+E). L'algorisme anterior és simplement DFS amb una pila addicional. Per tant, la complexitat del temps és la mateixa que DFS  
    Espai auxiliar:    O (V). Es necessita l'espai addicional per a la pila
 
    Ordenació topològica mitjançant BFS:    
C++ 
#include  #include  #include  using namespace std; // Class to represent a graph class Graph {  int V; // No. of vertices  list * adj; // Apuntador a una matriu que conté // llistes d'adjacència públiques: Graph(int V); // Constructor void addEdge(int v, int w); // Funció per afegir una vora al gràfic void topologicalSort(); // imprimeix un tipus topològic de // el gràfic complet }; Graph::Graph(int V) { this->V = V;  adj = llista nova [V]; } void Graph::addEdge(int v, int w) { adj[v].push_back(w); // Afegeix w a la llista de v. } // Funció per dur a terme l'ordenació topològica void Graph::topologicalSort() { // Crea un vector per emmagatzemar el vector en grau de tots els vèrtexs en_graus (V, 0);  // Travessa llistes d'adjacència per omplir_degree de // vèrtexs per (int v = 0; v< V; ++v) {  for (auto const& w : adj[v])  in_degree[w]++;  }  // Create a queue and enqueue all vertices with  // in-degree 0  queue q;  per (int i = 0; i< V; ++i) {  if (in_degree[i] == 0)  q.push(i);  }  // Initialize count of visited vertices  int count = 0;  // Create a vector to store topological order  vector ordre_superior;  // Treu els vèrtexs de la cua un per un // els vèrtexs adjacents si el grau d'adjacent passa a 0 mentre que (!q.empty()) { // Extreu la part davantera de la cua (o realitza la retirada de la cua) // i afegeix-ho a ordre topològic int u = q.front();  q.pop();  top_order.push_back(u);  // Iterar per tots els seus nodes veïns // del node u fora de cua i disminuir el seu grau // en 1 llista ::iterador itr;  for (itr = adj[u].begin(); itr != adj[u].end(); ++itr) // Si in-degree passa a zero, afegiu-lo a la cua si (--in_degree[*itr ] == 0) q.push(*itr);  comptar++;  } // Comprova si hi ha hagut un cicle if (count != V) { cout<< 'Graph contains cycle
';  return;  }  // Print topological order  for (int i : top_order)  cout << i << ' '; } // Driver code int main() {  // Create a graph given in the above diagram  Graph g(6);  g.addEdge(5, 2);  g.addEdge(5, 0);  g.addEdge(4, 0);  g.addEdge(4, 1);  g.addEdge(2, 3);  g.addEdge(3, 1);  cout << 'Following is a Topological Sort of the given '  'graph
';  g.topologicalSort();  return 0; }>
 Java 
import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; // Class to represent a graph class Graph {  private int V; // No. of vertices  private ArrayList [] adj; // Llista d'adjacència // representació de // el gràfic // Constructor Graph(int V) { this.V = V;  adj = nova ArrayList[V];  per (int i = 0; i< V; ++i)  adj[i] = new ArrayList();  }  // Function to add an edge to the graph  void addEdge(int v, int w)  {  adj[v].add(w); // Add w to v’s list.  }  // Function to perform Topological Sort  void topologicalSort()  {  // Create an array to store in-degree of all  // vertices  int[] inDegree = new int[V];  // Calculate in-degree of each vertex  for (int v = 0; v < V; ++v) {  for (int w : adj[v]) {  inDegree[w]++;  }  }  // Create a queue and enqueue all vertices with  // in-degree 0  Queue q = new LinkedList();  per (int i = 0; i< V; ++i) {  if (inDegree[i] == 0)  q.add(i);  }  // Initialize count of visited vertices  int count = 0;  // Create an ArrayList to store topological order  ArrayList topOrder = new ArrayList();  // Treu els vèrtexs de la cua un per un i // col·loqueu els vèrtexs adjacents si el grau de // adjacent es converteix en 0 mentre que (!q.isEmpty()) { // Extreu el front de la cua i afegiu-lo a // ordre topològic int u = q.poll();  topOrder.add(u);  comptar++;  // Itera per tots els seus nodes veïns del // node u de cua i disminueix el seu grau // en 1 per a (int w : adj[u]) { // Si el grau es converteix en zero, afegiu-lo a la // cua if (--inDegree[w] == 0) q.add(w);  } } // Comprova si hi ha hagut un cicle if (compte != V) { System.out.println('El gràfic conté el cicle');  tornar;  } // Imprimeix l'ordre topològic per a (int i : topOrder) System.out.print(i + ' ');  } } // Codi del controlador public class Main { public static void main(String[] args) { // Creeu un gràfic donat al diagrama anterior Graph g = new Graph(6);  g.addEdge(5, 2);  g.addEdge(5, 0);  g.addEdge(4, 0);  g.addEdge(4, 1);  g.addEdge(2, 3);  g.addEdge(3, 1);  System.out.println('El següent és una classificació topològica del gràfic donat');  g.topologicalSort();  } }>>>Python 3
 JavaScript 
// Class to represent a graph class Graph {  constructor(V) {  this.V = V; // No. of vertices  this.adj = new Array(V); // Array containing adjacency lists  for (let i = 0; i < V; i++) {  this.adj[i] = [];  }  }  // Function to add an edge to the graph  addEdge(v, w) {  this.adj[v].push(w); // Add w to v’s list.  }  // Function to perform Topological Sort  topologicalSort() {  // Create a array to store in-degree of all vertices  let inDegree = new Array(this.V).fill(0);  // Traverse adjacency lists to fill inDegree of vertices  for (let v = 0; v < this.V; v++) {  for (let w of this.adj[v]) {  inDegree[w]++;  }  }  // Create a queue and enqueue all vertices with in-degree 0  let queue = [];  for (let i = 0; i < this.V; i++) {  if (inDegree[i] === 0) {  queue.push(i);  }  }  // Initialize count of visited vertices  let count = 0;  // Create an array to store topological order  let topOrder = [];  // One by one dequeue vertices from queue and enqueue  // adjacent vertices if in-degree of adjacent becomes 0  while (queue.length !== 0) {  // Extract front of queue and add it to topological order  let u = queue.shift();  topOrder.push(u);  // Iterate through all its neighboring nodes  // of dequeued node u and decrease their in-degree by 1  for (let w of this.adj[u]) {  // If in-degree becomes zero, add it to queue  if (--inDegree[w] === 0) {  queue.push(w);  }  }  count++;  }  // Check if there was a cycle  if (count !== this.V) {  console.log('Graph contains cycle');  return;  }  // Print topological order  console.log('Topological Sort of the given graph:');  console.log(topOrder.join(' '));  } } // Driver code // Create a graph given in the above diagram let g = new Graph(6); g.addEdge(5, 2); g.addEdge(5, 0); g.addEdge(4, 0); g.addEdge(4, 1); g.addEdge(2, 3); g.addEdge(3, 1); console.log('Following is a Topological Sort of the given graph:'); g.topologicalSort(); //This code is contributed by Utkarsh>
   
  Sortida      Complexitat temporal:    
 
La complexitat temporal per construir el gràfic és O(V + E), on V és el nombre de vèrtexs i E és el nombre d'arestes.
 
La complexitat temporal per realitzar l'ordenació topològica mitjançant BFS també és O(V + E), on V és el nombre de vèrtexs i E és el nombre d'arestes. Això es deu al fet que cada vèrtex i cada aresta es visita una vegada durant el recorregut BFS.
 
    Complexitat espacial:    
b més arbre

 
La complexitat espacial per emmagatzemar el gràfic utilitzant una llista d'adjacència és O(V + E), on V és el nombre de vèrtexs i E és el nombre d'arestes.
 
S'utilitza espai addicional per emmagatzemar el grau de vèrtexs, que requereix espai O(V).
 
S'utilitza una cua per a la travessia BFS, que pot contenir com a màxim V vèrtexs. Així, la complexitat espacial de la cua és O(V).
 
En general, la complexitat espacial de l'algorisme és O (V + E) a causa de l'emmagatzematge del gràfic, la matriu en graus i la cua.
 
En resum, la complexitat temporal de la implementació proporcionada és O (V + E) i la complexitat espacial també és O (V + E).
 
    Nota:    Aquí, també podem utilitzar una matriu en lloc de la pila. Si s'utilitza la matriu, imprimiu els elements en ordre invers per obtenir l'ordenació topològica.
 
    Avantatges de l'ordenació topològica:    
  • Ajuda en la programació de tasques o esdeveniments basats en dependències.
  • Detecta cicles en un gràfic dirigit.
  • Eficient per resoldre problemes amb restriccions de precedència.
Desavantatges de l'ordenació topològica:
  • Només aplicable a gràfics acíclics dirigits (DAG), no aptes per a gràfics cíclics.
  • Pot no ser únic, poden existir múltiples ordenacions topològiques vàlides.
  • Ineficient per a gràfics grans amb molts nodes i arestes.
Aplicacions de l'ordenació topològica:
  • Programació de tasques i gestió de projectes.
  • Resolució de dependències en sistemes de gestió de paquets.
  • Determinació de l'ordre de compilació en sistemes de creació de programari.
  • Detecció de bloqueig en sistemes operatius.
  • Programació de cursos a les universitats.
    Articles relacionats:     
 
  •  Algorisme de Kahn per a l'ordenació topològica 
  •  Tots els tipus topològics d'un gràfic acíclic dirigit