Skip to content

Latest commit

 

History

History

Графы

readme.md

Графы

Оглавление

Теория

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

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

Пример: Например есть вот такой граф:

Граф

Линейное упорядочивание будет для этого графа вот таким:

Линейное упорядочивание

Для чего нужна топологическая сортировка:

  • Чтобы понять как обходить граф, если есть такая ситуация, что мы не можем выполнять некоторые действия до завершения других

Алгоритм

  1. Создаем массив для линейного упорядочивания, заполняем нулями

  2. Рассчитываем количество родителей каждой вершины

  3. Находим все родительские вершины, у них в полученном массиве будет 0 родителей

  4. Закидываем родителя в конец массива линейного упорядочивания, и у всех детей этой вершины уменьшаем количество родителей на 1. Если появились вершины, у которых кол-во родителей стало = 0, тогда эта вершина стала родительской и нужно опять проделать те же операции.

  5. Повторяем шаг 4 пока родители не закончатся, а потом фильтруем полученный массив от нулей

Время работы топологической сортировки О(n+m)

Кратчайший путь в ацикличном графе

Алгоритм

  1. Получаем линейное упорядочивание топологической сортировкой

  2. Создаем два массива shortest и pred - кратчайшие расстояния и кратчайшие пути

  3. Заполняем массив shortest бесконечностями, чтобы обозначить недосягаемые вершины, а массив pred значениями None.

  4. shortest[s] = 0, где s- стартовая вершина

  5. Перебираем все смежные вершины с вершинами из линейного упорядочивания и смотрим - нашелся ли путь короче, и заменяем.

Время работы алгоритма О(n+m)

Алгоритм Дейкстры

Алгоритм нужен для поиска кратчайшего пути между двумя точками.

Через неявную очередь с приоритетами

Алгоритм:

  1. Создаем два массива shortest и pred - кратчайшие расстояния и кратчайшие пути
  2. Заполняем массив shortest бесконечностями, чтобы обозначить недосягаемые вершины, а массив pred значениями None.
  3. Создаем множество Q, содержащее все вершины
  4. Организуем цикл: пока Q не пустое находим во множестве Q вершину с наименьшим значением в массиве shortest и удаляем ее из множества
  5. Перебираем все смежные вершины с удаленной из множества и меняем пути в массиве shortest на более короткие путем сравнения с начальным значением.