Топологичен алгоритъм за сортиране: Python, C++ Пример

Какво е алгоритъм за топологично сортиране?

Топологичното сортиране е известно още като алгоритъм на Кан и е популярен алгоритъм за сортиране. Използвайки насочена графа като вход, Topological Sort сортира възлите, така че всеки да се появява преди този, към който сочи.

Този алгоритъм се прилага върху DAG (насочен ацикличен граф), така че всеки възел се появява в подредения масив преди всички останали възли, към които сочи. Алгоритъмът следва някои правила многократно, докато сортирането не приключи.

За да опростите, вижте следния пример:

Насочена графика

Тук виждаме, че „A“ няма вътрешен градус. Вътрешният градус означава ръбът, който сочи към възел. „B“ и „C“ имат предпоставка за „A“, след което „E“ има предпоставка за възли „D“ и „F“. Някои от възлите са зависими от други възли.

Ето друго представяне на горната графика:

Зависимост на всеки възел (линейно подреждане)

Така че, когато предадем DAG (Directed Acyclic Graph) към топологичното сортиране, това ще ни даде масив с линеен ред, където първият елемент няма зависимост.

Ето стъпките за това:

Стъпка 1) Намерете възела с нула входящи ръбове, възел с нула градуса.

Стъпка 2) Съхранявайте този възел с нулева степен на входа в опашка или стек и премахнете възела от графиката.

Стъпка 3) След това изтрийте изходящия ръб от този възел. Това ще намали броя на градусите в следващия възел.

Топологичното подреждане изисква структурата от данни на графа да няма цикъл. Графът ще се счита за DAG, ако отговаря на следните изисквания:

• Един или повече възли със стойност на indegree нула.
• Графиката не съдържа никакъв цикъл.

Докато има възли в Графа и Графът все още е DAG, ще изпълним горните три стъпки. В противен случай алгоритъмът ще попадне в циклична зависимост и алгоритъмът на Кан няма да може да намери възел с нулева степен на входа.

Как работи топологичното сортиране

Тук ще използваме „алгоритъма на Кан“ за топологично сортиране. Да кажем, че имаме следния граф:

Ето стъпките за алгоритъма на Кан:

Стъпка 1) Изчислете обратната степен или входящия ръб на всички възли в графиката.

Забележка:

• Indegree означава насочените ръбове, сочещи към възела.
• Outdegree означава насочените ръбове, които идват от възел.

Ето вътрешната и външната степен на горната графика:

Стъпка 2) Намерете възела с нула вътрешни градуси или нула входящи ребра. Възел с нула вътрешна степен означава, че към този възел не идват ребра. Възел „A“ има нула вътрешни градуси, което означава, че няма ребро, сочещо към възел „A“. Така че ще извършим следните действия:

• Премахнете този възел и неговите изходящи ръбове.
• Поставете възела в опашката за поръчка.
• Актуализирайте броя на степените в съседния възел на „A“.

Стъпка 3) Трябва да намерим възел със стойност на входния градус нула. В този пример „B“ и „C“ имат нулева входна степен. Тук можем да вземем всеки от тези два. Нека вземем „B“ и го изтрием от Графа. След това актуализираме стойностите на входните степени на другите възли. След извършване на тези операции, нашият Граф и Опашка ще изглеждат по следния начин:

Стъпка 4) Възелът „C“ няма входящ ръб. Така че ще премахнем възела „C“ от графа и ще го поставим в опашката. Можем също да изтрием ръба, който е изходящ от „C“. Сега нашият граф ще изглежда така:

Стъпка 5) Виждаме, че възлите „D“ и „F“ имат входна степен нула. Ще вземем един възел и ще го поставим в опашката. Нека първо премахнем „D“. Тогава броят на входните степени за възел „E“ ще бъде 1. Сега няма да има възел от D до E. Трябва да направим същото за възел „F“ и резултатът ни ще бъде следният:

Стъпка 6) Входната степен (входящите ребра) и изходната степен (изходящите ребра) на възел „E“ станаха нула. Така че, ние изпълнихме всички предварителни изисквания за възел „E“. Тук ще поставим „E“ в края на опашката. Така че, нямаме останали възли и алгоритъмът приключва тук.

Прякор Code за топологично сортиране

Ето псевдокодът за топологично сортиране, използващ алгоритъма на Кан.

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 (насочен ацикличен граф), защото A, B и C създават цикъл. Ако забележите, няма възел с нулева стойност на входната степен. Според алгоритъма на Кан, ако анализираме горния граф:

• Намерете възел с нула входящи степени (без входящи ръбове).
• Премахнете този възел от графиката и го преместете в опашката. В горната графика обаче няма възел с нула градуси в инча. Всеки възел има стойност на градус в инча, по-голяма от 0.
• Връща празна опашка, тъй като не е намерен нито един възел с нула ин-градуси.

Можем да открием цикли, използвайки топологичното подреждане със следните стъпки:

Стъпка 1) Извършете топологично сортиране.

Стъпка 2) Изчислете общия брой елементи в топологично сортирания списък.

Стъпка 3) Ако броят на елементите е равен на общия брой на върховете, тогава няма цикъл.

Стъпка 4) Ако не е равен на броя на върховете, тогава в дадената графова структура от данни има поне един цикъл.

Анализ на сложността на топологично сортиране

Има два вида сложност в алгоритмите. Те са:

1. Сложност във времето
2. Сложност на пространството

Тези сложности са представени с функция, която осигурява обща сложност.

Времева сложност: Всички времеви сложности за топологичното сортиране са еднакви. Има най-лош, среден и най-добър сценарии за времева сложност. Времевата сложност за топологичното сортиране е O(E + V), където E означава броя на ребрата в графа, а V означава броя на върховете в графа.

Нека да преодолеем тази сложност:

Стъпка 1) В началото ще изчислим всички степени. За да направим това, трябва да преминем през всички ръбове и първоначално ще присвоим всички V върхове на нула. И така, постепенните стъпки, които изпълняваме, ще бъдат O(V+E).

Стъпка 2) Ще намерим възела с нулева стойност на indegree. Трябва да търсим от V числото на върха. И така, стъпките ще бъдат завършени O(V).

Стъпка 3) За всеки възел с нула indegrees, ние ще премахнем този възел и ще намалим indegrees. Извършването на тази операция за всички възли ще отнеме O(E).

Стъпка 4) Накрая ще проверим дали има някакъв цикъл или не. Ще проверим дали общият брой елементи в сортирания масив е равен на общия брой възли. Ще отнеме O (1).

И така, това бяха индивидуалните времеви сложности за всяка стъпка от топологичното сортиране или топологичното подреждане. Можем да кажем, че времевата сложност от горното изчисление ще бъде O(V + E); тук O означава функцията на сложност.

Космическа сложност: Нуждаехме се от O(V) пространства за изпълнение на алгоритъма за топологично сортиране. Ето стъпките, в които ни беше необходимо пространството за програмата:

• Трябваше да изчислим всички степени на възли, присъстващи в графиката. Тъй като Graph има общо V възли, трябва да създадем масив с размер V. Така че необходимото пространство беше O(V).
• Използвана е структура от данни на Queue за съхраняване на възела с нулева степен. Премахнахме възлите с нулева степен от оригиналната графика и ги поставихме в опашката. За това беше необходимото пространство O(V).
• Масивът е наречен „order“ (ред), който съхранява възлите в топологичен ред. Това също изисква O(V) пространства.

Това бяха индивидуалните пространствени сложности. Така че, трябва да максимизираме тези пространства по време на изпълнение. Пространствената сложност е O(V), където V означава номера на върха в графа.

Приложение на топологично сортиране

Топологичното сортиране има огромно приложение. Ето някои от тях:

• Използва се, когато един Operaтинг система трябва да извърши разпределението на ресурсите.
• Намиране на цикъл в графа. Можем да проверим дали графът е DAG или не чрез топологично сортиране.
• Подреждане на изречения в приложенията за автоматично довършване.
• Използва се за откриване безизходици.
• Различните видове планиране или планиране на курсове използват топологично сортиране.
• Разрешаване на зависимости. Например, ако се опитате да инсталирате пакет, този пакет може също да се нуждае от други пакети. Топологичното подреждане открива всички необходими пакети за инсталиране на текущия пакет.
• Linux използва топологичното сортиране в „apt“, за да провери зависимостта на пакетите.

Въпроси и Отговори