Направленный граф связности

Question

Для ориентированного графа G, каков наилучший способ найти вершину v, для которой существует путь от v до любой другой вершины в G?

Этот алгоритм должен работать за линейное время.Существует ли существующий алгоритм, который решает это?Если нет, я был бы признателен за понимание того, как это можно решить за линейное время (я могу думать только о решениях, которые, конечно, не будут занимать линейное время).

Answer 1

Составьте список L всех вершин.

Выберите одну;назовите его V. Из V, пройдитесь по графику, удаляя точки из списка по ходу и сохраняя стопку невидимых ребер.Когда вы найдете петлю (какой-то вершины, которую вы посещаете, нет в списке), вытолкните одно из ребер из стека и продолжайте.

Если стек пуст, а L не пуст, тогда выберите новыйвершина из L, назовите ее V и продолжайте как прежде.

Когда L, наконец, пусто, последний выбранный вами V является ответом.

Answer 2

Это можно сделать за линейное время по числу ребер.

1. Найти сильно связанные компоненты.
2. Сжатие каждого из компонентов в один узел.
3. Выполните топологическую сортировку на сжатом графе. Узел с самым высоким рангом будет иметь путь к каждому из других узлов (если граф вообще связан).

Answer 3

Я думаю, что получил правильный ответ.

1. Получить SCC.
2. Сжатие каждого из компонентов в один узел.
3. Проверьте, доступна ли каждая пара соседних узлов.

Это достаточное и необходимое условие.