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

Алгоритм топологической сортировки работает с 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), что равно общему количеству узлов в графе.

 

Применение:

1. Топологическая сортировка очень полезна для нахождения цикла графа.
2. Алгоритм топологической сортировки используется для определения условий взаимоблокировки в операционной системе.
3. Алгоритм топологической сортировки используется для поиска кратчайшего пути во взвешенном ациклическом графе.

 

Вывод :

В этой статье мы узнали еще об одном важном алгоритме — топологической сортировке. Мы видели, что этот алгоритм работает только с ациклическими графами. Алгоритм топологической сортировки также помогает определить порядок составления задачи. Алгоритм топологической сортировки имеет много преимуществ в реальном времени, например поиск кратчайшего пути. Поскольку топологическая сортировка чрезвычайно полезна, каждый программист и студент должен хорошо понимать этот алгоритм.