#algorithm #graph
#алгоритм #График
Вопрос:
Учитывая ориентированный граф G, каков наилучший способ найти вершину v такой, чтобы существовал путь от v до любой другой вершины в G?
Этот алгоритм должен выполняться за линейное время. Существует ли существующий алгоритм, который решает эту проблему? Если нет, я был бы признателен за некоторое представление о том, как это можно решить за линейное время (я могу думать только о решениях, которые, безусловно, не потребовали бы линейного времени).
Комментарии:
1. Ознакомьтесь с «Руководством по разработке алгоритмов» Скиенны. В нем есть прекрасная глава о графах.
Ответ №1:
Составьте список L всех вершин.
Выберите один; назовите его V. Из V пройдитесь по графику, удаляя точки из списка по мере продвижения и сохраняя стопку непросмотренных ребер. Когда вы найдете цикл (некоторой вершины, которую вы посещаете, нет в списке), извлеките одно из ребер из стека и продолжайте.
Если стек пуст, а L не пуст, выберите новую вершину из L, назовите ее V и продолжайте, как и раньше.
Когда L, наконец, пуст, V, которое вы выбрали последним, является ответом.
Комментарии:
1. Это вернет некоторый узел, даже если в графе нет узла, который фактически удовлетворяет условию. Я понятия не имею, имеет ли это значение для OP, но я думаю, что это следует упомянуть.
2. Да, это правда. Я думаю, вы можете проверить, достаточен ли ответ, попытавшись пройти по графику, начиная с него (это необходимо только в том случае, если вы не угадали это с первой попытки), снова отмечая все вершины по мере продвижения. Я полагаю, что это все равно будет линейным. И если тест завершается неудачей, решения нет.
Ответ №2:
Это может быть сделано за линейное время по числу ребер.
- Найдите сильно связанные компоненты.
- Сконденсируйте каждый из компонентов в один узел.
- Выполните топологическую сортировку на сжатом графе, узел с наивысшим рангом будет иметь путь к каждому из других узлов (если граф вообще подключен).
Ответ №3:
Я думаю, что у меня есть правильный ответ.
- Получить SCC.
- Сконденсируйте каждый из компонентов в один узел.
- Проверьте, достижима ли каждая пара смежных узлов.
Это достаточное и необходимое условие.