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

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

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

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

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

Σκηνοθετημένη Γράφημα

Εδώ, μπορούμε να δούμε ότι το «A» δεν έχει βαθμό indegree. Ο βαθμός Indegree σημαίνει την ακμή που δείχνει σε έναν κόμβο. Τα «B» και «C» έχουν προϋπόθεση το «A», τότε το «E» έχει προϋπόθεση τους κόμβους «D» και «F». Μερικοί από τους κόμβους εξαρτώνται από άλλους κόμβους.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Σημείωση:

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

Εδώ είναι ο βαθμός εισόδου και εξόδου του παραπάνω γραφήματος:

Βήμα 2) Βρείτε τον κόμβο με μηδενικές μοίρες εισόδου ή μηδενικές εισερχόμενες ακμές. Ο κόμβος με μηδενικό βαθμό εισόδου σημαίνει ότι δεν υπάρχουν ακμές που να έρχονται προς αυτόν τον κόμβο. Ο κόμβος "A" έχει μηδενικές μοίρες εισόδου, που σημαίνει ότι δεν υπάρχει ακμή που να δείχνει προς τον κόμβο "A". Επομένως, θα κάνουμε τις ακόλουθες ενέργειες:

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

Βήμα 3) Πρέπει να βρούμε έναν κόμβο με τιμή indegree μηδέν. Σε αυτό το παράδειγμα, οι κόμβοι "B" και "C" έχουν μηδενικό indegree. Εδώ, μπορούμε να πάρουμε οποιονδήποτε από αυτούς τους δύο. Ας πάρουμε τον "B" και ας τον διαγράψουμε από το Γράφημα. Στη συνέχεια, ας ενημερώσουμε τις τιμές indegree των άλλων κόμβων. Αφού εκτελέσουμε αυτές τις λειτουργίες, το Γράφημα και η Ουρά μας θα μοιάζουν με τα εξής:

Βήμα 4) Ο κόμβος «C» δεν έχει εισερχόμενη ακμή. Έτσι, θα αφαιρέσουμε τον κόμβο «C» από το Γράφημα και θα τον εισάγουμε στην Ουρά. Μπορούμε επίσης να διαγράψουμε την ακμή που εξέρχεται από το «C». Τώρα, το Γράφημά μας θα μοιάζει με αυτό:

Βήμα 5) Μπορούμε να δούμε ότι οι κόμβοι "D" και "F" έχουν μηδενικό βαθμό. Θα πάρουμε έναν κόμβο και θα τον βάλουμε στην ουρά. Ας αφαιρέσουμε πρώτα τον "D". Στη συνέχεια, ο αριθμός των βαθμών για τον κόμβο "E" θα είναι 1. Τώρα, δεν θα υπάρχει κόμβος από τον D στον E. Πρέπει να κάνουμε το ίδιο για τον κόμβο "F" και το αποτέλεσμά μας θα είναι το ακόλουθο:

Βήμα 6) Ο βαθμός εισόδου (εισερχόμενες ακμές) και ο βαθμός εξόδου (εξερχόμενες ακμές) του κόμβου "E" έγιναν μηδέν. Έτσι, έχουμε ικανοποιήσει όλες τις προϋποθέσεις για τον κόμβο "E". Εδώ, θα βάλουμε το "E" στο τέλος της ουράς. Έτσι, δεν έχουμε άλλους κόμβους και ο αλγόριθμος τελειώνει εδώ.

Παρατσούκλι Code για Τοπολογική Ταξινόμηση

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

Η τοπολογική ταξινόμηση μπορεί επίσης να εφαρμοστεί χρησιμοποιώντας το 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, αν αναλύσουμε το παραπάνω Γράφημα:

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

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

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

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

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

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

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

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

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

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

Χρόνος πολυπλοκότητας: Η χρονική πολυπλοκότητα είναι η ίδια για την Τοπολογική Ταξινόμηση. Υπάρχουν σενάρια χειρότερης, μέσης και βέλτιστης περίπτωσης για την χρονική πολυπλοκότητα. Η χρονική πολυπλοκότητα για την τοπολογική ταξινόμηση είναι 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).
• Ο πίνακας ονομάζεται «order», ο οποίος αποθήκευε τους κόμβους σε τοπολογική σειρά. Αυτό απαιτούσε επίσης O (V) χώρων.

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

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

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

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

Συχνές Ερωτήσεις