Как найти материнскую вершину в ориентированном графе в O (n + m)?

Question

Материнская вершина в ориентированном графе G = (V, E) - это вершина v такая, что все остальные вершины G могут быть достигнуты направленным путем из V Дайте алгоритм O (n + m), чтобы проверить, содержит ли граф G материнскую вершину.

(с) из руководства Skiena

Найден только O (n (n + m)) путь

Answer 1

При поиске, я действительно нашел ответ здесь .Если это домашнее задание, подумайте дважды, прежде чем заглядывать:)

Answer 2

Алгоритм ::

a) Выполните DFS / BFS графика и отследите последнюю законченную вершину 'x'.

б) Если существует какая-либо материнская вершина, то «х» является одной из них. Проверьте, является ли 'x' материнской вершиной, выполнив DFS / BFS из вершины 'x'.

Сложность времени O (n + m) + O (n + m) = O (n + m)

Answer 3

step1 . Делаем топологическую сортировку вершин ориентированного графа.

step2 . Теперь проверьте, можем ли мы достичь всех вершин из первой вершины топологически отсортированных вершин на шаге 1.

Чтобы выполнить шаг 2, снова инициализируйте массив обнаружил, что [i] ложно и выполняет dfs, начиная с первого узла топологически отсортированных вершин.

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

сложность времени: шаг 1 занимает O(n + m), шаг 2 занимает O(n + m) итого O(n+m) + O(n+m) = O(n+m)

Answer 4

Вот алгоритм поиска материнской вершины в графе, G = (VE):

1. Выполнить обход DFS данного графа.При выполнении обхода следите за последней законченной вершиной v.Этот шаг занимает время O (V + E).

2. Если существуют материнские вершины / вершины, то 'v' должно быть одним (или одним из них).Проверьте, является ли v материнской вершиной, выполнив DFS / BFS из v. Этот шаг также занимает время O (V + E).

Answer 5

мы можем найти материнскую вершину в O (m + n), используя алгоритм KOSARAJU

1. Сначала найдите DFS или BFS из любой вершины и отследите посещенную вершину и поместите ее в STACK.
2. Верхний элемент является материнской вершиной, если он может посещать все вершины, поэтому примените снова DFS или BFS.

См. Эту ссылку для DFS с использованием рекурсии и стека для отслеживания времени посещениявсех вершин

поэтому начните с вершины стека и заходите до тех пор, пока стек не станет пустым.Если есть единственная вершина, которая не посещена, то материнской вершины не существует.

Answer 6

1. Делаем топологическую сортировку на графике. Пример: A C D E B
2. Найти, существует ли путь от первого узла в топологическом порядке ко всем остальным узлам 2.а Инициализируйте расстояние от A до всех узлов как бесконечное и расстояние от A до A как 0. 2.b. Для всех узлов в топологическом порядке: Обновите кратчайшее расстояние для всех соседних узлов от A.
3. Обведите все узлы, чтобы увидеть, есть ли еще какое-то бесконечное расстояние. Если есть бесконечное расстояние, нет пути от A к этому узлу и возвращается false.
4. Если цикл по всем узлам выполнен успешно, вернуть true.

Answer 7

Я видел решение.Я не думаю, что нам нужно найти SCC.Просто сделайте DFS из случайной вершины, а затем сделайте DFS из вершины с последним временем окончания.Если есть материнская вершина, то это должно быть так.