Алгоритмы и структуры данных

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

Алгоритм, используемый для линейного упорядочения вершин ориентированного ациклического графа таким образом, что для каждого направленного ребра (u, v) вершина u предшествует вершине v в линейном порядке.

1. Инициализировать место, где вы будете хранить отсортированные вершины.
2. Выберите любую вершину без входящих ребер в качестве отправной точки.
3. Пока в графе есть необработанные вершины: Выберите вершину (v), у которой нет входящих ребер (степень 0), и удалите ее из графа. Добавьте вершину v в конец линейного порядка. Обновить степени соседних вершин (уменьшить на 1), поскольку вершина v была удалена.
4. Продолжайте шаг итерации, пока все вершины не будут обработаны.

Сложность: O(V + E)

www.tgoop.com/the_algorithms/4604

6.0K viewsNov 15, 2023 at 09:01

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

Алгоритм, используемый для линейного упорядочения вершин ориентированного ациклического графа таким образом, что для каждого направленного ребра (u, v) вершина u предшествует вершине v в линейном порядке.

1. Инициализировать место, где вы будете хранить отсортированные вершины.
2. Выберите любую вершину без входящих ребер в качестве отправной точки.
3. Пока в графе есть необработанные вершины: Выберите вершину (v), у которой нет входящих ребер (степень 0), и удалите ее из графа. Добавьте вершину v в конец линейного порядка. Обновить степени соседних вершин (уменьшить на 1), поскольку вершина v была удалена.
4. Продолжайте шаг итерации, пока все вершины не будут обработаны.

Сложность: O(V + E)

BY Алгоритмы и структуры данных