Топологическая сортировка: Python, C++ Пример алгоритма

Что такое алгоритм топологической сортировки?

Топологическая сортировка также известна как алгоритм Кана и является популярным алгоритмом сортировки. Используя ориентированный граф в качестве входных данных, топологическая сортировка сортирует узлы так, чтобы каждый из них появлялся перед тем, на который он указывает.

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

Для упрощения рассмотрим следующий пример:

Здесь мы видим, что у «А» нет восходящей степени. Это означает ребро, которое указывает на узел. «B» и «C» имеют предварительное условие «A», затем «E» имеет предварительное условие узлов «D» и «F». Некоторые узлы зависят от других узлов.

Вот еще одно представление приведенного выше графика:

Итак, когда мы передаем DAG (направленный ациклический граф) для топологической сортировки, он даст нам массив с линейным упорядочением, где первый элемент не имеет никаких зависимостей.

В этом примере показан график с циклом:

Вот шаги, которые нужно сделать:

Шаг 1) Найдите узел с нулевыми входящими ребрами, узел с нулевой степенью.

Шаг 2) Сохраните узел с нулевой степенью в очереди или стеке и удалите узел из графика.

Шаг 3) Затем удалите исходящее ребро из этого узла.

Это уменьшит количество градусов для следующего узла.

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

Граф будет считаться DAG, если он соответствует следующим требованиям:

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

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

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

Здесь мы будем использовать «Алгоритм Кана» для топологической сортировки. Допустим, у нас есть следующий график:

Вот шаги алгоритма Кана:

Шаг 1) Вычислите входящую степень или входящее ребро всех узлов графика.

Примечание:

• Подъем означает направленные ребра, указывающие на узел.
• Outgrade означает направленные ребра, исходящие из узла.

Вот входящая и исходящая степени приведенного выше графика:

Шаг 2) Найдите узел с нулевыми входными степенями или нулевыми входящими ребрами.

Узел с нулевым углом наклона означает, что к этому узлу не приближаются ребра. Узел «А» имеет нулевую степень, что означает, что нет ребра, указывающего на узел «А».

Итак, проделаем следующие действия:

• Удалите этот узел и его исходящие ребра (выходящие ребра).
• Поместите узел в Очередь на заказ.
• Обновите счетчик градусов соседнего узла «A».

Шаг 3) Нам нужно найти узел со значением входящей степени, равным нулю. В этом примере «B» и «C» имеют нулевой угол наклона.

Здесь мы можем взять любой из этих двух. Возьмем «Б» и удалим его из Графа.

Затем обновите значения степени других узлов.

После выполнения этих операций наш график и очередь будут выглядеть следующим образом:

Шаг 4) Узел «C» не имеет входящего ребра. Итак, мы удалим узел «C» из графика и поместим его в очередь.

Мы также можем удалить ребро, выходящее из «C».

Теперь наш график будет выглядеть так:

Шаг 5) Мы видим, что узлы «D» и «F» имеют нулевую степень. Мы возьмем узел и поместим его в очередь.

Давайте сначала вытащим букву «D». Тогда число входящих градусов для узла «E» будет равно 1. Теперь узла от D до E не будет.

Нам нужно сделать то же самое для узла «F», наш результат будет следующим:

Шаг 6) Степень входа (входящие ребра) и степень выхода (исходящие ребра) узла «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) Если оно не равно количеству вершин, то в данной структуре данных графа есть хотя бы один цикл.

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

В алгоритмах есть два типа сложности. Они

1. Сложность времени
2. Космическая сложность

Эти сложности представлены функцией, которая обеспечивает общую сложность.

Сложность времени: Для топологической сортировки вся временная сложность одинакова. Существуют худшие, средние и лучшие сценарии временной сложности.

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

Давайте разберемся с этой сложностью:

Шаг 1) Вначале мы вычислим все степени. Для этого нам нужно пройти через все ребра, и изначально мы присвоим всем входящим степеням вершин V нулевое значение. Итак, дополнительные шаги, которые мы выполним, будут О (В + Е).

Шаг 2) Мы найдем узел с нулевым значением угла наклона. Нам нужно искать по номеру V вершины. Итак, выполненные шаги будут О (В).

Шаг 3) Для каждого узла с нулевой восходящей степенью мы удалим этот узел и уменьшим восходящую степень. Выполнение этой операции для всех узлов займет О (Э).

Шаг 4) Наконец, мы проверим, есть ли цикл или нет. Мы проверим, равно ли общее количество элементов в отсортированном массиве общему количеству узлов. Это займет O (1).

Итак, это была индивидуальная временная сложность для каждого шага топологической сортировки или топологического упорядочения. Можно сказать, что временная сложность приведенного выше расчета составит O(V + E); здесь O означает функцию сложности.

Космическая сложность: Нам нужны были пространства O(V) для работы алгоритма топологической сортировки.

Вот шаги, где нам нужно место для программы:

• Нам пришлось вычислить все степени узлов, присутствующих в графике. Поскольку в графе всего V узлов, нам нужно создать массив размером V. Итак, необходимое пространство было О (В).
• Структура данных Queue использовалась для хранения узла с нулевой степенью входа. Мы удалили узлы с нулевым углом наклона из исходного графика и поместили их в очередь. Для этого необходимо было место. О (В).
• Массив называется «order». Это сохранило узлы в топологическом порядке. Это также требовало О (В) пространства.

Это были индивидуальные пространственные сложности. Итак, нам нужно максимизировать эти пространства во время выполнения.

Пространственная сложность обозначает O(V), где V означает номер вершины в графе.

Применение топологической сортировки

Топологическая сортировка имеет огромное применение. Вот некоторые из них:

• Используется, когда Operaсистема тинг необходимо выполнить распределение ресурсов.
• Нахождение цикла в графе. Мы можем проверить, является ли граф DAG или нет, с помощью топологической сортировки.
• Порядок предложений в приложениях с автозаполнением.
• Его используют для обнаружения тупики.
• Различные типы планирования или планирования курсов используют топологическую сортировку.
• Разрешение зависимостей. Например, если вы попытаетесь установить пакет, для этого пакета также могут потребоваться другие пакеты. Топологическое упорядочение определяет все необходимые пакеты для установки текущего пакета.
• Linux использует топологическую сортировку в «apt» для проверки зависимости пакетов.