Топологическая сортировка в Python с элементами Моголов

Топологическая сортировка в Python с элементами Моголов

Моголы правили Южной Азией около двух столетий и оказали огромное влияние на Индийский субконтинент. Один из таких примеров - Тадж-Махал. В этом блоге мы будем использовать генеалогическое древо империи Великих Моголов, чтобы понять топологическую сортировку в теории графов.

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

Топологическая сортировка, которая также известна как топологическое упорядочение в ориентированном ациклическом графе (DAG), - это линейное упорядочение вершин, такое что для каждого ребра UV от вершины U до вершины V U идет перед V в упорядочении.

Выполнение сортировки топологии на генеалогическом дереве с именами членов семьи в качестве вершин дерева приведет к тому, что сначала будет обрабатываться поколение 1 семейства, а затем поколение 2.

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

Рассмотрим алгоритм реализации топологической сортировки,

• Инициализация структуры данных для определения графа:
  Для топологической сортировки нам нужно инициализировать связь между вершинами (родитель-потомок) и степенью каждой вершины. Используя отношения родитель-потомок между вершинами, можно создать список смежности графа.
  Независимость требуется для вывода зависимости между вершинами. Если вершина имеет нулевую степень степени, это означает, что в эту вершину нет входящего ребра и она не зависит от какой-либо другой вершины.
  В коде для хранения графа и степени используется словарь. Его также можно представить как класс.

indegree = {i: 0 for i in vertices}
graph = {i: [] for i in vertices}

• Заполнение степени и графа:
  Из заданного набора ребер обновите словарь графа, указав список смежности и степень для каждой вершины.

for edge in edges:
    parent, child = edge[0], edge[1]
    graph[parent].append(child)
    indegree[child] += 1

• Добавление вершин с нулевой степенью в очередь:
  Вершина с нулевой степенью не зависит от других вершин. Добавьте его в очередь для дальнейшей обработки.

sources = deque()
for source, degree in indegree.items():
    # store vertex with indegree zero
    if degree == 0:
    sources.append(source)

• Обработка вершин, добавленных в очередь:
  Извлечь вершину из очереди и обработать все дочерние вершины извлеченной вершины. Дочерняя вершина добавляется в очередь, если степень становится равной нулю.

while sources:
    source = sources.popleft()
    sortedOrder.append(source)
    for child in graph[source]:
    # decrement indegree of child vertex
        indegree[child] -= 1
        # if indegree is zero then add it to the queue
        if indegree[child] == 0:
            sources.append(child)

• Проверка наличия петель между вершинами:
  Будет цикл, если вершина A зависит от вершины B, а вершина B зависит от вершины A, так что и вершина A, и вершина B всегда будут имеют степень 1 и никогда не будут обрабатываться топологической сортировкой. Циклы можно обнаружить, сравнив длину sorted_list и длину словаря графа. Если после выполнения топологической сортировки не все вершины добавлены в sorted_list, это означает, что несколько вершин имели степень, отличную от нуля, даже после удаления всех зависимостей.

if len(sortedOrder) != len(vertices):
    return list()

Ниже приведен код Python для топологической сортировки.

Вывод вышеуказанной программы:

Topological sort: ['Babur', 'Humayun', 'Askari', 'Akbar', 'Mirza', 'Jahangir', 'Daniyal', 'Shah Jahan', 'Khusrau', 'Aurangzeb', 'Murad']

Где использовать топологическую сортировку:

• Порядок вершин:
  Это можно использовать для устранения зависимости между несколькими элементами. Например, установка пакетов, в которых один пакет является необходимым условием для установки другого пакета.
• Нахождение петли на графике:
  Это продолжение вышеупомянутой точки. Например, вершина A зависит от вершины B, вершина B зависит от вершины C, а вершина C зависит от вершины A. Это создает петлю между вершинами A, B и C. Для обнаружения таких петель можно использовать топологическую сортировку. В приведенном выше примере кода это достигается в строке №44.

Интересные факты об империи Великих Моголов

• Тадж-Махал был построен Шахом Джаханом и является одним из шедевров мирового наследия.
• Император Хумаюн был отстранен от власти, но он боролся вопреки всему, чтобы вернуть себе империю, что является большим уроком для всех. Преодолеть препятствия всегда можно упорным трудом.
• Император Акбар считался дислексиком.

P.S. Пример, обсуждаемый в этом блоге, также может быть решен с использованием BFS, потому что мы обрабатываем дерево (частный случай графа). Я выбрал топологическую сортировку, чтобы объяснить алгоритм.

Спасибо, что читаете блог. Надеюсь, он был вам полезен.