Топологічний сорт: Python, C++ Приклад алгоритму

Що таке алгоритм топологічного сортування?

Топологічне сортування також відоме як алгоритм Кана і є популярним алгоритмом сортування. Використовуючи орієнтований граф як вхідні дані, топологічне сортування сортує вузли так, що кожен з’являється перед тим, на який він вказує.

Цей алгоритм застосовується до DAG (спрямованого ациклічного графіка), щоб кожен вузол з’являвся в упорядкованому масиві до того, як усі інші вузли вказували на нього. Цей алгоритм повторює певні правила, доки сортування не завершиться.

Щоб спростити, подивіться на такий приклад:

Тут ми бачимо, що «А» не має ступеня. Це означає ребро, яке вказує на вузол. «B» і «C» мають передумову «A», тоді «E» має передумову «D» і «F» вузлів. Деякі з вузлів залежать від інших вузлів.

Ось ще одне представлення наведеного вище графіка:

Залежність кожного вузла (лінійне впорядкування)

Отже, коли ми передаємо DAG (спрямований ациклічний граф) до топологічного сортування, це дасть нам масив із лінійним упорядкуванням, де перший елемент не має залежності.

У цьому прикладі показано графік із циклом:

Щоб це зробити, виконайте наведені нижче дії.

Крок 1) Знайдіть вузол з нульовими вхідними ребрами, вузол з нульовими градусами.

Крок 2) Зберігайте цей нульовий вузол у черзі або стеку та видаляйте вузол із графіка.

Крок 3) Потім видаліть вихідне ребро з цього вузла.

Це зменшить кількість ступенів для наступного вузла.

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

Графік вважатиметься DAG, якщо він відповідає таким вимогам:

Один або кілька вузлів із нульовим значенням незмінного ступеня.
Граф не містить жодного циклу

Поки на графіку є вузли, а графік все ще є групою DAG, ми виконаємо описані вище три кроки. В іншому випадку алгоритм потрапить у циклічну залежність, і алгоритм Кана не зможе знайти вузол із нульовим ступенем.

Як працює топологічне сортування

Тут ми будемо використовувати «алгоритм Кана» для топологічного сортування. Припустимо, ми маємо такий графік:

Ось кроки для алгоритму Кана:

Крок 1) Обчисліть прямий градус або вхідне ребро всіх вузлів на графіку.

Примітка:

Indegree означає спрямовані ребра, що вказують на вузол.
Зовнішній ступінь означає спрямовані ребра, які виходять з вузла.

Ось прямий і зворотний ступінь наведеного вище графіка:

Крок 2) Знайдіть вузол із нульовим прямим градусом або нульовими вхідними ребрами.

Вузол із нульовим прямим градусом означає, що до цього вузла не приходять ребра. Вузол «А» має нуль вхідних градусів, тобто немає ребра, що вказує на вузол «А».

Отже, будемо виконувати такі дії:

Видалити цей вузол і його крайні межі (вихідні ребра)
Помістити вузол в Чергу на замовлення.
Оновіть кількість градусів сусіднього вузла «A».

Крок 3) Нам потрібно знайти вузол зі значенням неступеневого ступеня, рівним нулю. У цьому прикладі «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 (Пошук спочатку на глибину) метод. Однак цей підхід є рекурсивним методом. Алгоритм Кана ефективніший, ніж підхід 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 вершини indegrees до нуля. Отже, поетапні кроки, які ми виконуємо, будуть O(V+E).

Крок 2) Ми знайдемо вузол із нульовим значенням ступеня. Нам потрібно шукати з V номеру вершини. Отже, кроки будуть виконані O(V).

Крок 3) Для кожного вузла з нульовим індексом ми видалимо цей вузол і зменшимо індекс. Виконання цієї операції для всіх вузлів займе O(E).

Крок 4) Нарешті, ми перевіримо, чи є цикл чи ні. Ми перевіримо, чи дорівнює загальна кількість елементів у відсортованому масиві загальній кількості вузлів. Це займе O (1).

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

Складність простору: Нам потрібні були простори O(V) для запуску алгоритму топологічного сортування.

Ось кроки, на яких нам знадобився простір для програми:

Нам потрібно було обчислити всі ступені вузлів, присутніх на графіку. Оскільки граф має загальну кількість V вузлів, нам потрібно створити масив розміром V. Отже, необхідний простір був O(V).
Для зберігання вузла з нульовим ступенем була використана структура даних Queue. Ми видалили вузли з нульовим ступенем з оригінального графіка та розмістили їх у черзі. Для цього необхідний простір був O(V).
Масив називається «порядок». Це зберігає вузли в топологічному порядку. Це теж було потрібно O(V) простори.

Це були індивідуальні просторові складності. Отже, нам потрібно максимізувати ці простори під час виконання.

Просторова складність означає O(V), де V означає номер вершини в графі.

Застосування топологічного сортування

Топологічне сортування має величезне застосування. Ось деякі з них:

Використовується при Operaсистема тингу необхідно виконати розподіл ресурсів.
Знаходження циклу в графі. Ми можемо перевірити, чи є граф DAG чи ні, за допомогою топологічного сортування.
Упорядкування речень у програмах для автозавершення.
Його використовують для виявлення тупики.
Інші типи планування або планування курсу використовують топологічне сортування.
Вирішення залежностей. Наприклад, якщо ви спробуєте встановити пакет, для цього пакета також можуть знадобитися інші пакети. Топологічне впорядкування визначає всі необхідні пакети для встановлення поточного пакета.
Linux використовує топологічне сортування в «apt», щоб перевірити залежність пакетів.

Вам може сподобатися:

Що таке алгоритм топологічного сортування?

Як працює топологічне сортування

Псевдокод для топологічного сортування

СТАТТІ ПО ТЕМІ

C++ Реалізація топологічного сортування

Вихід

Python Реалізація топологічного сортування

Вихід

Циклічні графи алгоритму топологічного сортування

Аналіз складності топологічного сортування

Застосування топологічного сортування