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

Топологическая сортировка дает линейный порядок вершин в ориентированном ациклическом графе так, что для каждого ориентированного ребра a -> b вершина ‘a’ предшествует вершине ‘b’. Помните, что ориентированный ациклический граф имеет по крайней мере одну вершину с начальной степенью 0 и одну вершину с исходящей степенью 0.

Может быть несколько топологических упорядочение для ориентированного ациклического графа.

Алгоритм Кана

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

В алгоритме Кана задействованы следующие шаги:

Вспомогательные переменные:

  1. массив («temp») для хранения результата o f этап предварительной обработки.

  2. переменная («посещенная») для хранения количества посещенных вершин.

  3. строка («результат») для хранения топологического порядка сортировки.

Предварительная обработка:

Вычислите внутреннюю степень каждой вершины графа и сохраните их в массиве «temp».

Фактические шаги:

  1. Поместите вершины в очередь с внутренней степенью 0.

  2. Пока очередь не пуста:

    2.1. Удаление вершины из очереди.

    2.2. Добавьте эту вершину к результату.

    2.3. Увеличьте переменную «посещено» на 1.

    2.4. Уменьшите внутреннюю степень всех его соседних вершин на 1 в массиве «temp».

    2.5 Поместите соседние вершины в очередь с внутренней степенью 0.

  3. Если значение переменной «посещено» равно количеству вершин в графе, то граф действительно направлен и ацикличен, и результат будет содержать топологическую сортировку для графа.

На следующем рисунке показан алгоритм в действии:

Направленный ациклический граф.

1 из 12

Оцените статью
nanomode.ru
Добавить комментарий