Алгоритмы и структуры данных@the_algorithms P.4618

THE_ALGORITHMS Telegram 4618

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

Алгоритм Тарьяна

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

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

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

www.tgoop.com/the_algorithms/4618

6.2K viewsNov 30, 2023 at 09:04

tgoop.com/the_algorithms/4618

Create: 2023-11-30
Last Update: 2025-07-01 01:29:48

Алгоритм Тарьяна

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

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

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

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

Share with your friend now:
tgoop.com/the_algorithms/4618

Open in Telegram

Telegram News

Date: 2025-07-01|

It’s easy to create a Telegram channel via desktop app or mobile app (for Android and iOS): Ng Man-ho, a 27-year-old computer technician, was convicted last month of seven counts of incitement charges after he made use of the 100,000-member Chinese-language channel that he runs and manages to post "seditious messages," which had been shut down since August 2020. Polls Telegram channels enable users to broadcast messages to multiple users simultaneously. Like on social media, users need to subscribe to your channel to get access to your content published by one or more administrators. Telegram desktop app: In the upper left corner, click the Menu icon (the one with three lines). Select “New Channel” from the drop-down menu.
from us

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