Algorytm sortowania topologicznego: Python, C++ Przykład

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.

Ten algorytm jest stosowany do DAG (Directed Acyclic Graph – ukierunkowanego grafu acyklicznego), tak aby każdy węzeł pojawiał się w uporządkowanej tablicy przed wszystkimi innymi węzłami, na które wskazuje. Algorytm ten powtarza pewne reguły, aż do zakończenia sortowania.

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

Kierowany wykres

Tutaj widzimy, że „A” nie ma stopnia wejściowego. Stopień wejściowy oznacza krawędź wskazującą na węzeł. „B” i „C” mają warunek wstępny w postaci węzłów „A”, a „E” ma warunek wstępny w postaci 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:

Zależność każdego węzła (porządkowanie liniowe)

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.

Oto kroki, aby to zrobić:

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

Krok 2) Zapisz węzeł o zerowym stopniu wejściowym w kolejce lub stosie i usuń węzeł z grafu.

Krok 3) Następnie usuń krawędź wychodzącą z tego węzła. Spowoduje to zmniejszenie liczby stopni wejściowych dla następnego węzła.

Porządkowanie topologiczne wymaga, aby struktura danych grafu nie zawierała żadnego cyklu. Graf 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.
• Na wykresie nie ma żadnego cyklu.

Dopóki graf zawiera węzły i graf nadal jest DAG-iem, wykonamy powyższe trzy kroki. W przeciwnym razie algorytm popadnie 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ń wejściowy i wyjściowy powyższego wykresu:

Krok 2) Znajdź węzeł z zerowym stopniem wejściowym lub zerową liczbą krawędzi przychodzących. Węzeł z zerowym stopniem wejściowym oznacza, że ​​nie ma krawędzi zbliżających się do niego. Węzeł „A” ma zerowy stopień wejściowy, co oznacza, że ​​nie ma krawędzi wskazującej na węzeł „A”. Wykonamy zatem następujące czynności:

• Usuń ten węzeł i jego krawędzie wychodzące.
• Umieść węzeł w kolejce do zamówienia.
• Zaktualizuj liczbę stopni wejściowych węzła sąsiedniego „A”.

Krok 3) Musimy znaleźć węzeł z wartością stopnia wejściowego równą zero. W tym przykładzie „B” i „C” mają zerowy stopień wejściowy. Możemy wybrać dowolny z nich. Weźmy „B” i usuńmy go z grafu. Następnie zaktualizujmy wartości stopni wejściowych pozostałych węzłów. Po wykonaniu tych operacji nasz graf i kolejka będą wyglądać następująco:

Krok 4) Węzeł „C” nie ma krawędzi przychodzącej. Dlatego usuniemy węzeł „C” z grafu i umieścimy go w kolejce. Możemy również usunąć krawędź wychodzącą z „C”. Teraz nasz graf będzie wyglądał następująco:

Krok 5) Widzimy, że węzły „D” i „F” mają stopień wejściowy równy zero. Weźmy węzeł i umieścimy go w kolejce. Najpierw usuńmy „D”. Wtedy liczba stopni wejściowych dla węzła „E” wyniesie 1. Teraz nie będzie żadnego węzła od D do E. Musimy zrobić to samo dla węzła „F”, a nasz wynik będzie wyglądał następująco:

Krok 6) Stopień wejściowy (krawędzie przychodzące) i stopień wyjściowy (krawędzie wychodzące) węzła „E” stały się równe zero. Spełniliśmy zatem wszystkie wymagania wstępne dla węzła „E”. W tym przypadku umieścimy „E” na końcu kolejki. Nie mamy już żadnych węzłów i algorytm kończy się w tym miejscu.

Rzekomy Code do sortowania topologicznego

Poniżej znajduje się 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 0 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

Graf zawierający cykl nie może być uporządkowany topologicznie, ponieważ graf cykliczny ma zależność w sposób cykliczny. Na przykład, spójrz na ten graf:

Ten graf nie jest skierowanym grafem acyklicznym (DAG), ponieważ A, B i C tworzą cykl. Zauważ, że nie ma węzła o zerowej wartości stopnia wejściowego. Zgodnie z algorytmem Kahna, jeśli przeanalizujemy powyższy graf:

• Znajdź węzeł o zerowych stopniach (bez krawędzi przychodzących).
• Usuń ten węzeł z Grafu i przenieś go do Kolejki. Jednak na powyższym Grafie nie ma węzła o zerowych stopniach wejściowych. Każdy węzeł ma wartość stopnia wejściowego większą niż 0.
• Zwróć pustą kolejkę, ponieważ nie można znaleźć żadnego węzła o zerowych stopniach wejściowych.

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żeli liczba elementów jest równa całkowitej liczbie wierzchołków, to cykl nie istnieje.

Krok 4) Jeśli nie jest ona równa liczbie wierzchołków, to w danej strukturze danych grafu istnieje 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: Złożoność czasowa sortowania topologicznego jest taka sama. 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.

Przełammy 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).

Oto zatem 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 wyniesie O(V + E); tutaj O oznacza funkcję złożoności.

Złożoność przestrzeni: Potrzebowaliśmy przestrzeni O(V) do uruchomienia algorytmu sortowania topologicznego. Oto kroki, w których potrzebowaliśmy tej przestrzeni dla programu:

• 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”, co oznacza, że ​​węzły są przechowywane w kolejności topologicznej. Wymagało to również O (V) spacje.

To były indywidualne złożoności przestrzenne. Musimy więc zmaksymalizować te przestrzenie w czasie wykonania. Złożoność przestrzenna to O(V), gdzie V oznacza numer wierzchołka w grafie.

Zastosowanie sortowania topologicznego

Sortowanie topologiczne ma ogromne zastosowanie. Oto niektóre z nich:

• Używa się go, gdy Operasystem tingu musi przeprowadzić alokację zasobów.
• Znajdowanie cyklu w grafie. Możemy sprawdzić, czy graf jest DAG-iem, czy nie, za pomocą sortowania topologicznego.
• Porządkowanie zdań w aplikacjach do automatycznego uzupełniania.
• Służy do wykrywania zakleszczenia.
• Różne typy harmonogramowania lub harmonogramowania kursów wykorzystują 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.

FAQ