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

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

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

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

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

Направленный график

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

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

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

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

Вот шаги, чтобы сделать это:

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

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

Шаг 3) Затем удалите исходящее ребро от этого узла. Это уменьшит число входящих связей для следующего узла.

Для обеспечения топологического упорядочения структура данных графа не должна содержать циклов. Граф будет считаться направленным ациклическим графом (DAG), если он соответствует этим требованиям:

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

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

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

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

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

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

Примечание:

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

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

Шаг 2) Найдите узел с нулевой входящей степенью или нулевым количеством входящих ребер. Узел с нулевой входящей степенью означает, что к нему не ведут никакие ребра. Узел «А» имеет нулевую входную степень, то есть к узлу «А» не ведут никакие ребра. Поэтому мы выполним следующие действия:

• Удалите этот узел и его исходящие ребра (ребра, указывающие на степень его сходства).
• Поместите узел в Очередь на заказ.
• Обновите количество входящих связей соседнего узла узла «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 нулевое значение. Итак, дополнительные шаги, которые мы выполним, будут О (В + Е).

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

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

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

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

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

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

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

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

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

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

Часто задаваемые вопросы (FAQ)