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

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

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

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

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

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

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

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

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

Този пример показва графика с цикъл:

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

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

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

Стъпка 3) След това изтрийте изходящия ръб от този възел.

Това ще намали броя на градуса за следващия възел.

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

Една графика ще се счита за DAG, ако следва следните изисквания:

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

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

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

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

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

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

Забележка:

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

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

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

Възелът с нулева степен означава, че няма ръбове, които идват към този възел. Възел „А“ има нула впръсквания, което означава, че няма ръб, сочещ към възел „А“.

И така, ще извършим следните действия:

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

Стъпка 3) Трябва да намерим възел със стойност на indegree нула. В този пример "B" и "C" имат нулева степен.

Тук можем да вземем едно от двете. Нека вземем "B" и го изтрием от графиката.

След това актуализирайте стойностите на indegree на други възли.

След извършване на тези операции нашата графика и опашка ще изглеждат по следния начин:

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

Можем също да изтрием ръба, който излиза от „C“.

Сега нашата графика ще изглежда така:

Стъпка 5) Можем да видим, че възлите "D" и "F" имат нулева степен. Ще вземем възел и ще го поставим в опашката.

Нека първо извадим „D“. Тогава броят на страничните степени за възел „E“ ще бъде 1. Сега няма да има възел от D до E.

Трябва да направим същото за възел „F“, нашият резултат ще бъде като следното:

Стъпка 6) Indegree (входящи ръбове) и outdegree (изходящи ръбове) на възел "E" станаха нула. И така, изпълнихме всички предпоставки за възел „E“.

Тук поставяме „E“ в края на опашката. И така, нямаме останали възли, така че алгоритъмът приключва тук.

Псевдо код за топологично сортиране

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

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

Според алгоритъма на Кан, ако анализираме горната графика:

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

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

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

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

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

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

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

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

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

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

Времева сложност: Цялата времева сложност е еднаква за топологичното сортиране. Има най-лош, среден и най-добър сценарии за времева сложност.

Времевата сложност за топологично сортиране е 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).
Масивът се нарича „поръчка“. Това съхраняваше възлите в топологичен ред. Това също се изискваше O(V) пространства.

Това бяха индивидуалните пространствени сложности. Така че трябва да увеличим максимално тези пространства по време на изпълнение.

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

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

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

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

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

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

Псевдо код за топологично сортиране

СВЪРЗАНИ СТАТИИ

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

Продукция

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

Продукция

Циклични графи на алгоритъм за топологично сортиране

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

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

Регистрирайте се за бюлетина