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

Алгоритм Косараджу (Косарайю)

Алгоритм, используемый для определения сильно связных компонент в ориентированном графе.

Алгоритм:
1. Начните с произвольной вершины в графе и выполните обход в глубину, отмечая каждую вершину временным меткой времени первого прохода.
2. Перейдите к обратному графу (поменяйте направление всех ребер).
3. Сортируйте вершины в порядке убывания их временной метки первого прохода.
4. Снова выполните обход в глубину, но на этот раз в порядке отсортированных вершин.
5. Каждый получившийся обход в глубину будет формировать сильно связную компоненту.

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

www.tgoop.com/the_algorithms/4619

6.0K viewsDec 1, 2023 at 09:00

Алгоритм Косараджу (Косарайю)

Алгоритм, используемый для определения сильно связных компонент в ориентированном графе.

Алгоритм:
1. Начните с произвольной вершины в графе и выполните обход в глубину, отмечая каждую вершину временным меткой времени первого прохода.
2. Перейдите к обратному графу (поменяйте направление всех ребер).
3. Сортируйте вершины в порядке убывания их временной метки первого прохода.
4. Снова выполните обход в глубину, но на этот раз в порядке отсортированных вершин.
5. Каждый получившийся обход в глубину будет формировать сильно связную компоненту.

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

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