Sortowanie topologiczne: Python, C++ Przykład algorytmu

Co to jest algorytm sortowania topologicznego?

Sortowanie topologiczne jest również znane jako algorytm Kahna i jest popularnym algorytmem sortowania. Wykorzystując graf skierowany jako dane wejściowe, sortowanie topologiczne sortuje węzły w taki sposób, że każdy pojawia się przed tym, na który wskazuje.

Algorytm ten jest stosowany w DAG (kierunkowym grafie acyklicznym), dzięki czemu każdy węzeł pojawia się w uporządkowanej tablicy, zanim zostaną na niego wskazane wszystkie inne węzły. Algorytm ten kieruje się pewnymi regułami wielokrotnie, aż do zakończenia sortowania.

Dla uproszczenia przyjrzyjmy się poniższemu przykładowi:

Widzimy tutaj, że „A” nie ma stopnia wyższego. Oznacza krawędź wskazującą na węzeł. „B” i „C” mają warunek wstępny „A”, następnie „E” ma warunek wstępny węzłów „D” i „F”. Niektóre węzły są zależne od innych węzłów.

Oto inna reprezentacja powyższego wykresu:

Zatem, gdy przekazujemy DAG (Skierowany Graf Acykliczny) do sortowania topologicznego, otrzymamy tablicę o uporządkowaniu liniowym, w której pierwszy element nie ma zależności.

Ten przykład pokazuje wykres z cyklem:

Oto kroki, jak to zrobić:

Krok 1) Znajdź węzeł z zerowymi krawędziami przychodzącymi i węzeł z zerowymi stopniami.

Krok 2) Store, który zeruje węzeł stopnia w kolejce lub stosie i usuwa węzeł z wykresu.

Krok 3) Następnie usuń wychodzącą krawędź z tego węzła.

Spowoduje to zmniejszenie liczby stopni dla następnego węzła.

Porządek topologiczny wymaga, aby struktura danych wykresu nie miała żadnego cyklu.

Wykres zostanie uznany za DAG, jeśli spełnia następujące wymagania:

• Jeden lub więcej węzłów o wartości stopnia równej zero.
• Wykres nie zawiera żadnego cyklu

Dopóki w Grafie są węzły i Graf jest nadal DAG, będziemy wykonywać powyższe trzy kroki. W przeciwnym razie algorytm wpadnie w zależność cykliczną, a algorytm Kahna nie będzie w stanie znaleźć węzła o zerowym stopniu wejściowym.

Jak działa sortowanie topologiczne

Tutaj użyjemy „Algorytmu Kahna” do sortowania topologicznego. Załóżmy, że mamy następujący Graf:

Oto kroki algorytmu Kahna:

Krok 1) Oblicz stopień wejściowy lub krawędź dochodzącą wszystkich węzłów na wykresie.

Uwaga:

• Stopień oznacza skierowane krawędzie wskazujące na węzeł.
• Stopień zewnętrzny oznacza skierowane krawędzie wychodzące z węzła.

Oto stopień początkowy i końcowy powyższego wykresu:

Krok 2) Znajdź węzeł z zerowymi stopniami lub zerowymi krawędziami przychodzącymi.

Węzeł o zerowym stopniu oznacza, że ​​w kierunku tego węzła nie zbliżają się żadne krawędzie. Węzeł „A” ma zerowe stopnie, co oznacza, że ​​nie ma krawędzi wskazującej na węzeł „A”.

Więc wykonamy następujące czynności:

• Usuń ten węzeł i jego krawędzie stopnia zewnętrznego (krawędzie wychodzące)
• Umieść węzeł w kolejce do zamówienia.
• Zaktualizuj liczbę stopni w sąsiednim węźle „A”.

Krok 3) Musimy znaleźć węzeł o wartości stopnia równej zero. W tym przykładzie „B” i „C” mają zerowy stopień.

Tutaj możemy wziąć którykolwiek z tych dwóch. Weźmy „B” i usuńmy je z wykresu.

Następnie zaktualizuj wartości stopni innych węzłów.

Po wykonaniu tych operacji nasz wykres i kolejka będą wyglądać następująco:

Krok 4) Węzeł „C” nie ma krawędzi przychodzącej. Zatem usuniemy węzeł „C” z wykresu i wepchniemy go do kolejki.

Możemy także usunąć krawędź wychodzącą z „C”.

Teraz nasz wykres będzie wyglądał następująco:

Krok 5) Widzimy, że węzły „D” i „F” mają stopień zerowy. Weźmiemy węzeł i umieścimy go w kolejce.

Najpierw usuńmy „D”. Wtedy liczba stopni dla węzła „E” będzie wynosić 1. Teraz nie będzie żadnego węzła od D do E.

Musimy zrobić to samo dla węzła „F”, nasz wynik będzie wyglądał następująco:

Krok 6) Stopień wejściowy (krawędzie wychodzące) i stopień wyjściowy (krawędzie wychodzące) węzła „E” osiągnęły wartość zerową. Zatem spełniliśmy wszystkie wymagania wstępne dla węzła „E”.

Tutaj stawiamy „E” na końcu kolejki. Nie mamy już żadnych węzłów, więc algorytm kończy się w tym miejscu.

Pseudokod sortowania topologicznego

Oto pseudokod sortowania topologicznego przy użyciu algorytmu Kahna.

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

Sortowanie topologiczne można również wdrożyć za pomocą DFS (Głębokie pierwsze wyszukiwanie) metoda. Jednak to podejście jest metodą rekurencyjną. Algorytm Kahna jest bardziej wydajny niż podejście DFS.

C++ Implementacja sortowania topologicznego

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

Wydajność

0       1       2       3       5       4

Python Implementacja sortowania topologicznego

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

Wydajność

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

Wykresy cykliczne algorytmu sortowania topologicznego

Grafu zawierającego cykl nie można uporządkować topologicznie. Ponieważ wykres cykliczny ma zależność w sposób cykliczny.

Na przykład sprawdź ten wykres:

Ten wykres nie jest DAG (ukierunkowany wykres acykliczny), ponieważ A, B i C tworzą cykl. Jeśli zauważysz, nie ma węzła o zerowej wartości stopnia.

Zgodnie z algorytmem Kahna, jeśli przeanalizujemy powyższy wykres:

• Znajdź węzeł o zerowych stopniach (bez krawędzi przychodzących).
• Usuń ten węzeł z wykresu i przesuń go do kolejki.
  Jednak na powyższym wykresie nie ma węzła z zerem w stopniach. Każdy węzeł ma wartość stopnia większą niż 0.
• Zwróć pustą kolejkę, ponieważ nie mogła znaleźć żadnego węzła z zerem w stopniach.

Możemy wykryć cykle, stosując porządkowanie topologiczne, wykonując następujące kroki:

Krok 1) Wykonaj sortowanie topologiczne.

Krok 2) Oblicz całkowitą liczbę elementów na liście posortowanej topologicznie.

Krok 3) Jeśli liczba elementów jest równa całkowitej liczbie wierzchołków, to nie ma cyklu.

Krok 4) Jeśli nie jest równa liczbie wierzchołków, to w danej strukturze danych grafu występuje co najmniej jeden cykl.

Analiza złożoności sortowania topologicznego

Istnieją dwa rodzaje złożoności algorytmów. Są to:

1. Złożoność czasowa
2. Złożoność przestrzeni

Złożoności te są reprezentowane przez funkcję zapewniającą ogólną złożoność.

Złożoność czasowa: Cała złożoność czasowa jest taka sama dla sortowania topologicznego. Istnieją najgorsze, średnie i najlepsze scenariusze złożoności czasowej.

Złożoność czasowa sortowania topologicznego wynosi O(E + V), gdzie E oznacza liczbę krawędzi w grafie, a V oznacza liczbę wierzchołków w grafie.

Przeanalizujmy tę złożoność:

Krok 1) Na początku obliczymy wszystkie stopnie. Aby to zrobić, musimy przejść przez wszystkie krawędzie i początkowo przypiszemy wszystkie stopnie wierzchołków V do zera. Zatem kolejne kroki, które wykonamy, będą takie O(V+E).

Krok 2) Znajdziemy węzeł o zerowej wartości stopnia. Musimy szukać od numeru V wierzchołka. Tak więc kroki zostaną ukończone O (V).

Krok 3) Dla każdego węzła z zerowymi stopniami wejściowymi usuniemy ten węzeł i zmniejszymy stopień wejściowy. Wykonanie tej operacji dla wszystkich węzłów zajmie O(E).

Krok 4) Na koniec sprawdzimy, czy istnieje jakiś cykl, czy nie. Sprawdzimy, czy całkowita liczba elementów w posortowanej tablicy jest równa całkowitej liczbie węzłów. To zajmie O (1).

Tak więc, to były indywidualne złożoności czasowe dla każdego kroku sortowania topologicznego lub porządkowania topologicznego. Możemy powiedzieć, że złożoność czasowa z powyższego obliczenia będzie wynosić O( V + E ); tutaj O oznacza funkcję złożoności.

Złożoność przestrzeni: Do uruchomienia algorytmu sortowania topologicznego potrzebowaliśmy przestrzeni O(V).

Oto kroki, w których potrzebowaliśmy miejsca na program:

• Musieliśmy obliczyć wszystkie stopnie węzłów obecnych na wykresie. Ponieważ wykres ma w sumie V węzłów, musimy utworzyć tablicę o rozmiarze V. Zatem wymagana przestrzeń wynosiła O (V).
• Do przechowywania węzła z zerowym stopniem wykorzystano strukturę danych Queue. Usunęliśmy węzły o zerowym stopniu z oryginalnego wykresu i umieściliśmy je w kolejce. W tym celu wymagana była przestrzeń O (V).
• Tablica nosi nazwę „order”. To przechowywało węzły w porządku topologicznym. To też było wymagane O (V) spacje.

To była indywidualna złożoność przestrzeni. Więc musimy zmaksymalizować te przestrzenie w czasie wykonywania.

Złożoność przestrzenna oznacza O(V), gdzie V oznacza numer wierzchołka w grafie.

Zastosowanie sortowania topologicznego

Sortowanie topologiczne ma ogromne zastosowanie. Tutaj jest kilka z nich:

• Używa się go, gdy Operasystem tingu musi przeprowadzić alokację zasobów.
• Znalezienie cyklu na grafie. Możemy sprawdzić, czy wykres jest typu DAG, czy nie, za pomocą sortowania topologicznego.
• Porządkowanie zdań w aplikacjach do automatycznego uzupełniania.
• Służy do wykrywania zakleszczenia.
• Inny typ planowania lub planowania kursu wykorzystuje sortowanie topologiczne.
• Rozwiązywanie zależności. Na przykład, jeśli spróbujesz zainstalować pakiet, ten pakiet może również potrzebować innych pakietów. Porządkowanie topologiczne wyszukuje wszystkie pakiety niezbędne do zainstalowania bieżącego pakietu.
• Linux używa sortowania topologicznego w „apt”, aby sprawdzić zależności pakietów.