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

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

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

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

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

Орієнтований граф

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

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

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

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

Ось кроки, як це зробити:

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

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

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

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

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

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

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

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

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

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

Примітка:

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

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

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

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

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

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

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

Поширені запитання