Алгоритм топологической сортировки работает с DAG (прямой ациклический граф). Смысл топологической сортировки в том, что если какой-либо узел указывает на другой узел, то после него будет идти узел, указывающий на другой узел. Таким образом, в этом случае, если у нас есть циклический граф, мы не можем предсказать, какой узел после какого узла. Вот почему алгоритм топологической сортировки работает только с ациклическим графом, а не с циклическим графом.
Каждый граф имеет более одной топологической последовательности сортировки, поскольку она зависит от степени вхождения ребер узлов. Первый начальный узел, который мы выбираем с числом узлов в степени, равен 0.
Давайте разберемся с алгоритмом топологической сортировки на примере.
Шаг 1: мы вставляем те узлы, количество входящих ребер которых равно 0. Таким образом, эти узлы являются узлами 1 и 4.
Шаг 2:
а. Начнем с узла 1. Мы можем выбрать любой узел между узлами 1 и 4.
б. Мы уменьшаем каждое ребро узла на 1, которое связано с узлом 1. Мы уменьшаем ребро узлов (0, 2 и 3).
в. Мы перемещаем узел 1 из списка в топологически отсортированный список, как показано ниже.
Шаг 3:
а. Теперь мы исходим из списка, который является Node 4.
б. Мы уменьшаем все исходящие ребра узлов, соединенных с узлом 4, которые являются узлами (0 и 3).
в. Теперь узел 3 не имеет входящих ребер, поэтому мы помещаем его в список, а узел 4 переходит в топологически отсортированный список.
Шаг 4:
а. Теперь мы исходим из списка, который является узлом 3.
б. Мы уменьшаем все исходящие ребра узлов, соединенных с узлом 3, которые являются узлами (0 и 2).
в. Теперь узлы 0 и 2 не имеют входящих ребер, поэтому мы помещаем их в список, а узел 3 переходит в топологически отсортированный список.
Шаг 5:
а. Теперь мы исходим из списка, который является Node 0.
б. Поскольку исходящих ребер из Node 0 нет, мы просто добавляем их в список топологической сортировки.
Шаг 6:
а. Теперь мы исходим из списка, который является узлом 2.
б. Поскольку исходящих ребер из узла 2 нет, мы просто добавляем их в список топологической сортировки.
Шаг 7:
Наконец, мы отсортировали список здесь.
Алгоритм топологической сортировки
Ниже приведены шаги алгоритма топологической сортировки, которым мы должны следовать.
Шаг 0: Рассчитайте степень вхождения каждого узла графа.
Шаг 1: Сначала нам нужно найти узел, у которого входящие ребра равны нулю.
Шаг 2: мы удаляем этот узел из графа и добавляем его в список топологических порядков сортировки.
Шаг 3: Удалите те узлы, у которых есть исходящие ребра.
Шаг 4: Уменьшите степень вхождения на количество связанных ребер, которые были удалены.
Шаг 5: Повторяйте шаги 1–4, пока не останется узлов с нулевой степенью вхождения.
Шаг 6: Убедитесь, что все элементы расположены в правильной последовательности.
Шаг 7: Теперь мы отсортировали заказ из шага 6.
Шаг 8: Положите конец алгоритму.
Код Python : ниже приведена реализация приведенного выше примера на Python.
fromcollectionsimportdefaultdict classbuildGraph : def__init__(self, nodes : int) : self.nodes= nodes # Теперь мы сохраняем граф в формате смежного списка self.adjListDetails=defaultdict(list) # Он будет хранить информацию о входящих ребрах определенного узла # в самом self.count_numbers_of_incoming_edge_of_a_node= [] # Мы сохраняем отсортированные узлы в топологическом порядке self.topological_sorted_order= [] # Мы храним информацию обо всех тех узлах, которые # не имеют входящих ребер в графе self.nodes_have_zero_incoming_edges= [] # Теперь мы создаем смежный список всех графов для сортировки defAddGraphEdge (self, source :int, destination : int) : self.adjListDetails[source].append(destination) self.count_numbers_of_incoming_edge_of_a_node[destination] +=1 defTopologicalSortAlgorithm (self) : for node inrange(self.nodes) : ifself.count_numbers_of_incoming_edge_of_a_node[node] ==0 : self.nodes_have_zero_incoming_edges.append(node) whileself.nodes_have_zero_incoming_edges : self.nodes_have_zero_incoming_edges.sort() source =self.nodes_have_zero_incoming_edges.pop(0) # итерация по соседнему списку if source inself.adjListDetails : for node inself.adjListDetails[source] : self.count_numbers_of_incoming_edge_of_a_node[node] -=1 ifself.count_numbers_of_incoming_edge_of_a_node[node] ==0 : self.nodes_have_zero_incoming_edges.append(node) self.topological_sorted_order.append(source) print("Топологический порядок сортировки: "+str(self.topological_sorted_order)) defmain() : number_of_nodes=7 graph =buildGraph(number_of_nodes) graph.count_numbers_of_incoming_edge_of_a_node= [0] *number_of_nodes graph.AddGraphEdge(0,2) graph.AddGraphEdge(0,5) graph.AddGraphEdge(1,3) graph.AddGraphEdge(1,6) graph.AddGraphEdge(2,4) graph.AddGraphEdge(3,5) graph.AddGraphEdge(5,2) graph.AddGraphEdge(5,4) graph.AddGraphEdge(6,2) graph.TopologicalSortAlgorithm() if __name__ =="__main__" : main()
Выход:
Топологический порядок сортировки: [0, 1, 3, 5, 6, 2, 4]
Временная сложность алгоритма топологической сортировки:
Общее время обработки алгоритма равно O (E + N), где E представляет количество ребер, а N представляет количество узлов в графе. Затем, на следующем шаге, мы должны вычислить степень входа каждого узла, что обычно занимает O(E) раз, а затем поместить все эти узлы в отсортированный список, где их степень входа равна нулю, что занимает O(N) раз. раз. Таким образом, общая временная сложность алгоритма топологической сортировки составляет O (E+N).
Но пространственная сложность алгоритма топологической сортировки составляет O (N), что равно общему количеству узлов в графе.
Применение:
- Топологическая сортировка очень полезна для нахождения цикла графа.
- Алгоритм топологической сортировки используется для определения условий взаимоблокировки в операционной системе.
- Алгоритм топологической сортировки используется для поиска кратчайшего пути во взвешенном ациклическом графе.
Вывод :
В этой статье мы узнали еще об одном важном алгоритме — топологической сортировке. Мы видели, что этот алгоритм работает только с ациклическими графами. Алгоритм топологической сортировки также помогает определить порядок составления задачи. Алгоритм топологической сортировки имеет много преимуществ в реальном времени, например поиск кратчайшего пути. Поскольку топологическая сортировка чрезвычайно полезна, каждый программист и студент должен хорошо понимать этот алгоритм.