Τοπολογική ταξινόμηση: Python, C++ Παράδειγμα αλγορίθμου

Τι είναι ο αλγόριθμος τοπολογικής ταξινόμησης;

Η τοπολογική ταξινόμηση είναι επίσης γνωστή ως αλγόριθμος του Kahn και είναι ένας δημοφιλής αλγόριθμος ταξινόμησης. Χρησιμοποιώντας ένα κατευθυνόμενο γράφημα ως είσοδο, η Τοπολογική Ταξινόμηση ταξινομεί τους κόμβους έτσι ώστε ο καθένας να εμφανίζεται πριν από αυτόν στον οποίο δείχνει.

Αυτός ο αλγόριθμος εφαρμόζεται σε ένα DAG (Directed Acyclic Graph) έτσι ώστε κάθε κόμβος να εμφανίζεται στον ταξινομημένο πίνακα πριν από όλους τους άλλους κόμβους στραμμένους σε αυτόν. Αυτός ο αλγόριθμος ακολουθεί ορισμένους κανόνες επανειλημμένα μέχρι να ολοκληρωθεί η ταξινόμηση.

Για απλοποίηση, δείτε το ακόλουθο παράδειγμα:

Εδώ, μπορούμε να δούμε ότι το "Α" δεν έχει βαθμό. Σημαίνει την άκρη που δείχνει σε έναν κόμβο. Το "B" και το "C" έχουν προαπαιτούμενο το "A", τότε το "E" έχει προαπαιτούμενο τους κόμβους "D" και "F". Μερικοί από τους κόμβους εξαρτώνται από άλλους κόμβους.

Ακολουθεί μια άλλη αναπαράσταση του παραπάνω Γραφήματος:

Εξάρτηση κάθε Κόμβου — Εξάρτηση κάθε κόμβου (γραμμική σειρά)

Έτσι, όταν περάσουμε το DAG (Directed Acyclic Graph) στην τοπολογική ταξινόμηση, θα μας δώσει έναν πίνακα με γραμμική διάταξη, όπου το πρώτο στοιχείο δεν έχει καμία εξάρτηση.

Αυτό το παράδειγμα δείχνει ένα γράφημα με έναν κύκλο:

Εδώ είναι τα βήματα για να το κάνετε αυτό:

Βήμα 1) Βρείτε τον κόμβο με μηδέν εισερχόμενες άκρες, έναν κόμβο με μηδέν μοίρες.

Βήμα 2) Αποθηκεύστε ότι μηδενίζει τον κόμβο σε βαθμό σε μια ουρά ή στοίβα και αφαιρεί τον κόμβο από το γράφημα.

Βήμα 3) Στη συνέχεια, διαγράψτε την εξερχόμενη άκρη από αυτόν τον κόμβο.

Αυτό θα μειώσει το πλήθος βαθμών για τον επόμενο κόμβο.

Η τοπολογική σειρά απαιτεί ότι η δομή δεδομένων γραφήματος δεν θα έχει κανένα κύκλο.

Ένα γράφημα θα θεωρείται DAG εάν ακολουθεί αυτές τις απαιτήσεις:

Ένας ή περισσότεροι κόμβοι με τιμή indegree μηδέν.
Το γράφημα δεν περιέχει κανένα κύκλο

Όσο υπάρχουν κόμβοι στο Γράφημα και το Γράφημα εξακολουθεί να είναι DAG, θα εκτελέσουμε τα παραπάνω τρία βήματα. Διαφορετικά, ο αλγόριθμος θα εμπίπτει στην κυκλική εξάρτηση και ο Αλγόριθμος του Kahn δεν θα μπορεί να βρει έναν κόμβο με μηδέν σε βαθμό.

Πώς λειτουργεί η Τοπολογική Ταξινόμηση

Εδώ, θα χρησιμοποιήσουμε τον «Αλγόριθμο του Καν» για την τοπολογική ταξινόμηση. Ας πούμε ότι έχουμε το ακόλουθο Γράφημα:

Ακολουθούν τα βήματα για τον αλγόριθμο του Kahn:

Βήμα 1) Υπολογίστε το indegree ή το εισερχόμενο άκρο όλων των κόμβων στο γράφημα.

Σημείωση:

Indegree σημαίνει τις κατευθυνόμενες άκρες που δείχνουν προς τον κόμβο.
Outdegree σημαίνει τα κατευθυνόμενα άκρα που προέρχονται από έναν κόμβο.

Ακολουθεί το indegree και το outdegree του παραπάνω γραφήματος:

Βήμα 2) Βρείτε τον κόμβο με μηδέν μοίρες ή μηδέν εισερχόμενες ακμές.

Ο κόμβος με μηδέν indegree σημαίνει ότι δεν έρχονται άκρες προς αυτόν τον κόμβο. Ο κόμβος "Α" έχει μηδέν μοίρες, που σημαίνει ότι δεν υπάρχει άκρη που να δείχνει στον κόμβο "Α".

Έτσι, θα κάνουμε τις παρακάτω ενέργειες:

Αφαιρέστε αυτόν τον κόμβο και τις ακμές του ανώτερου βαθμού (εξερχόμενες άκρες)
Τοποθετήστε τον κόμβο στην ουρά για παραγγελία.
Ενημερώστε το πλήθος βαθμών του γειτονικού κόμβου του "A".

Βήμα 3) Πρέπει να βρούμε έναν κόμβο με μηδενική τιμή indegree. Σε αυτό το παράδειγμα, το "B" και το "C" έχουν μηδενικό βαθμό.

Εδώ, μπορούμε να πάρουμε ένα από αυτά τα δύο. Ας πάρουμε το "Β" και ας το διαγράψουμε από το Γράφημα.

Στη συνέχεια, ενημερώστε τις τιμές indegree άλλων κόμβων.

Αφού εκτελέσουμε αυτές τις λειτουργίες, το Γράφημα και η ουρά μας θα μοιάζουν με τα εξής:

Βήμα 4) Ο κόμβος "C" δεν έχει εισερχόμενη άκρη. Έτσι, θα αφαιρέσουμε τον κόμβο "C" από το γράφημα και θα τον σπρώξουμε στην ουρά.

Μπορούμε επίσης να διαγράψουμε το άκρο που είναι εξερχόμενο από το "C".

Τώρα, το Γράφημά μας θα μοιάζει με αυτό:

Βήμα 5) Μπορούμε να δούμε ότι οι κόμβοι "D" και "F" έχουν τον βαθμό μηδέν. Θα πάρουμε έναν κόμβο και θα τον βάλουμε στην ουρά.

Ας βγάλουμε πρώτα το "D". Τότε ο αριθμός βαθμών για τον κόμβο "E" θα είναι 1. Τώρα, δεν θα υπάρχει κανένας κόμβος από το D στο E.

Πρέπει να κάνουμε το ίδιο για τον κόμβο "F", το αποτέλεσμά μας θα είναι το εξής:

Βήμα 6) Το indegree (εισερχόμενες άκρες) και το outdegree (εξερχόμενες άκρες) του κόμβου "E" έγιναν μηδέν. Έτσι, έχουμε εκπληρώσει όλα τα προαπαιτούμενα για τον κόμβο «Ε».

Εδώ, βάζουμε το "E" στο τέλος της ουράς. Έτσι, δεν έχουμε κανέναν κόμβο, οπότε ο αλγόριθμος τελειώνει εδώ.

Ψευδοκώδικας για τοπολογική ταξινόμηση

Εδώ είναι ο ψευδοκώδικας για την τοπολογική ταξινόμηση κατά τη χρήση του αλγόριθμου του 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

Η τοπολογική ταξινόμηση μπορεί επίσης να εφαρμοστεί χρησιμοποιώντας το DFS (Πρώτη αναζήτηση βάθους) μέθοδος. Ωστόσο, αυτή η προσέγγιση είναι η αναδρομική μέθοδος. Ο αλγόριθμος του Kahn είναι πιο αποτελεσματικός από την προσέγγιση DFS.

C++ Εφαρμογή Τοπολογικής Διαλογής

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

Παραγωγή

0       1       2       3       5       4

Python Εφαρμογή Τοπολογικής Διαλογής

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

Παραγωγή

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

Κυκλικά γραφήματα αλγόριθμου τοπολογικής ταξινόμησης

Ένα γράφημα που περιέχει έναν κύκλο δεν μπορεί να ταξινομηθεί τοπολογικά. Καθώς το κυκλικό γράφημα έχει την εξάρτηση με κυκλικό τρόπο.

Για παράδειγμα, ελέγξτε αυτό το γράφημα:

Αυτό το γράφημα δεν είναι DAG (Directed Acyclic Graph) επειδή τα A, B και C δημιουργούν έναν κύκλο. Εάν παρατηρήσετε, δεν υπάρχει κόμβος με μηδενική τιμή σε βαθμό.

Σύμφωνα με τον αλγόριθμο του Kahn, αν αναλύσουμε το παραπάνω γράφημα:

Βρείτε έναν κόμβο με μηδέν μοίρες (χωρίς εισερχόμενες ακμές).
Αφαιρέστε αυτόν τον κόμβο από το γράφημα και σπρώξτε τον στην ουρά.
Ωστόσο, στο παραπάνω Γράφημα, δεν υπάρχει κόμβος με μηδέν σε μοίρες. Κάθε κόμβος έχει μια τιμή βαθμού μεγαλύτερη από 0.
Επιστρέψτε μια κενή ουρά, καθώς δεν μπορούσε να βρει κανέναν κόμβο με μηδέν σε μοίρες.

Μπορούμε να ανιχνεύσουμε κύκλους χρησιμοποιώντας την τοπολογική σειρά με τα ακόλουθα βήματα:

Βήμα 1) Εκτελέστε τοπολογική ταξινόμηση.

Βήμα 2) Υπολογίστε τον συνολικό αριθμό των στοιχείων στην τοπολογικά ταξινομημένη λίστα.

Βήμα 3) Εάν ο αριθμός των στοιχείων ισούται με τον συνολικό αριθμό των κορυφών, τότε δεν υπάρχει κύκλος.

Βήμα 4) Εάν δεν είναι ίσο με τον αριθμό των κορυφών, τότε υπάρχει τουλάχιστον ένας κύκλος στη δεδομένη δομή δεδομένων γραφήματος.

Ανάλυση πολυπλοκότητας Τοπολογικής Ταξινόμησης

Υπάρχουν δύο τύποι πολυπλοκότητας στους αλγόριθμους. Είναι

Χρόνος πολυπλοκότητας
Διαστημική πολυπλοκότητα

Αυτές οι πολυπλοκότητες αντιπροσωπεύονται με μια συνάρτηση που παρέχει μια γενική πολυπλοκότητα.

Χρόνος πολυπλοκότητας: Η πολυπλοκότητα του χρόνου είναι ίδια για την Τοπολογική Ταξινόμηση. Υπάρχουν τα χειρότερα, τα μέτρια και τα καλύτερα σενάρια για την πολυπλοκότητα του χρόνου.

Η χρονική πολυπλοκότητα για την τοπολογική ταξινόμηση είναι O(E + V), εδώ, το E σημαίνει τον αριθμό των ακμών στο γράφημα και το V σημαίνει τον αριθμό των κορυφών στο γράφημα.

Ας ξεπεράσουμε αυτήν την πολυπλοκότητα:

Βήμα 1) Στην αρχή θα υπολογίσουμε όλους τους βαθμούς. Για να γίνει αυτό, πρέπει να περάσουμε από όλες τις ακμές και αρχικά, θα αντιστοιχίσουμε όλους τους βαθμούς V κορυφής στο μηδέν. Έτσι, τα σταδιακά βήματα που ολοκληρώνουμε θα είναι O(V+E).

Βήμα 2) Θα βρούμε τον κόμβο με μηδενική τιμή βαθμών. Πρέπει να ψάξουμε από τον αριθμό V της κορυφής. Έτσι, τα βήματα που θα ολοκληρωθούν θα είναι O (V).

Βήμα 3) Για κάθε κόμβο με μηδέν μοίρες, θα αφαιρέσουμε αυτόν τον κόμβο και θα μειώσουμε τον βαθμό. Η εκτέλεση αυτής της λειτουργίας για όλους τους κόμβους θα χρειαστεί O(E).

Βήμα 4) Τέλος, θα ελέγξουμε αν υπάρχει κύκλος ή όχι. Θα ελέγξουμε αν ο συνολικός αριθμός των στοιχείων στον ταξινομημένο πίνακα είναι ίσος με τον συνολικό αριθμό των κόμβων. Θα πάρει Ο (1).

Έτσι, αυτές ήταν η ατομική χρονική πολυπλοκότητα για κάθε βήμα της τοπολογικής ταξινόμησης ή τοπολογικής ταξινόμησης. Μπορούμε να πούμε ότι η χρονική πολυπλοκότητα από τον παραπάνω υπολογισμό θα είναι O( V + E ); Εδώ, το O σημαίνει τη συνάρτηση πολυπλοκότητας.

Διαστημική πολυπλοκότητα: Χρειαζόμασταν κενά O(V) για την εκτέλεση του αλγόριθμου τοπολογικής ταξινόμησης.

Ακολουθούν τα βήματα όπου χρειαζόμασταν τον χώρο για το πρόγραμμα:

Έπρεπε να υπολογίσουμε όλους τους βαθμούς των κόμβων που υπάρχουν στο Γράφημα. Καθώς το γράφημα έχει συνολικά V κόμβους, πρέπει να δημιουργήσουμε έναν πίνακα μεγέθους V. Άρα, ο χώρος που απαιτείται ήταν O (V).
Μια δομή δεδομένων ουράς χρησιμοποιήθηκε για την αποθήκευση του κόμβου με μηδενικό βαθμό. Αφαιρέσαμε τους κόμβους με μηδέν indegree από το αρχικό Graph και τους τοποθετήσαμε στην ουρά. Για αυτό ήταν ο απαιτούμενος χώρος O (V).
Ο πίνακας ονομάζεται "παραγγελία". Αυτό αποθήκευε τους κόμβους σε τοπολογική σειρά. Αυτό απαιτούσε επίσης O (V) χώρων.

Αυτές ήταν η ατομική πολυπλοκότητα του χώρου. Επομένως, πρέπει να μεγιστοποιήσουμε αυτούς τους χώρους στο χρόνο εκτέλεσης.

Η πολυπλοκότητα χώρου σημαίνει O(V), όπου V σημαίνει τον αριθμό της κορυφής στο γράφημα.

Εφαρμογή Τοπολογικής Ταξινόμησης

Υπάρχει τεράστια χρήση για την Τοπολογική Ταξινόμηση. Εδώ είναι μερικά από αυτά:

Χρησιμοποιείται όταν Operaσύστημα ting πρέπει να εκτελέσει την κατανομή πόρων.
Εύρεση κύκλου στο γράφημα. Μπορούμε να επικυρώσουμε εάν το Γράφημα είναι DAG ή όχι με τοπολογική ταξινόμηση.
Ταξινόμηση προτάσεων στις εφαρμογές αυτόματης συμπλήρωσης.
Χρησιμοποιείται για ανίχνευση αδιέξοδα.
Διαφορετικός τύπος Προγραμματισμού ή προγραμματισμού μαθημάτων χρησιμοποιεί την τοπολογική ταξινόμηση.
Επίλυση εξαρτήσεων. Για παράδειγμα, εάν προσπαθήσετε να εγκαταστήσετε ένα πακέτο, αυτό το πακέτο ενδέχεται να χρειάζεται και άλλα πακέτα. Η τοπολογική σειρά βρίσκει όλα τα απαραίτητα πακέτα για την εγκατάσταση του τρέχοντος πακέτου.
Linux χρησιμοποιεί την τοπολογική ταξινόμηση στο "apt" για να ελέγξει την εξάρτηση των πακέτων.

Τι είναι ο αλγόριθμος τοπολογικής ταξινόμησης;

Πώς λειτουργεί η Τοπολογική Ταξινόμηση

Ψευδοκώδικας για τοπολογική ταξινόμηση

ΣΧΕΤΙΚΑ ΑΡΘΡΑ

C++ Εφαρμογή Τοπολογικής Διαλογής

Παραγωγή

Python Εφαρμογή Τοπολογικής Διαλογής

Παραγωγή

Κυκλικά γραφήματα αλγόριθμου τοπολογικής ταξινόμησης

Ανάλυση πολυπλοκότητας Τοπολογικής Ταξινόμησης

Εφαρμογή Τοπολογικής Ταξινόμησης

Εγγραφείτε στο ενημερωτικό δελτίο