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

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

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

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

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

www.tgoop.com/the_algorithms/4643

5.6K viewsDec 18, 2023 at 09:00

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

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

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

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

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