Блог

Главная - Вопросы по программированию - Направленная связность графа

Направленная связность графа

#algorithm #graph

#алгоритм #График

Вопрос:

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

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

Комментарии:

1. Ознакомьтесь с «Руководством по разработке алгоритмов» Скиенны. В нем есть прекрасная глава о графах.

Ответ №1:

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

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

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

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

Комментарии:

1. Это вернет некоторый узел, даже если в графе нет узла, который фактически удовлетворяет условию. Я понятия не имею, имеет ли это значение для OP, но я думаю, что это следует упомянуть.

2. Да, это правда. Я думаю, вы можете проверить, достаточен ли ответ, попытавшись пройти по графику, начиная с него (это необходимо только в том случае, если вы не угадали это с первой попытки), снова отмечая все вершины по мере продвижения. Я полагаю, что это все равно будет линейным. И если тест завершается неудачей, решения нет.

Ответ №2:

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

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

Ответ №3:

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

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

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