Обнаружение стока в ориентированном ациклическом графе

Question

Допустим, в DAG есть одна вершина со следующим свойством:

1. Все вершины связаны с ней

2. Он не связан с какой-либо вершиной

Это обычно называется вершиной-приемником .

Возможно ли обнаружитьэта вершина в O(n), где n - количество вершин в графе?

Answer 1

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

После того, как вы прошли n шагов (или меньше, и вы не можете продолжить), поскольку проблема не гарантирует, что есть раковина, вы должны проверить, если вы в одном. Это добавляет еще O(n). Таким образом, проблема O(2 n) = O(n)

Answer 2

Лучшее, что я могу придумать, это O(n + m), что составляет O(n), если m равно O(n).

Предполагая, что сток существует, выполните топологическую сортировку графа.Минимальный узел в сортировке - это приемник.Обратите внимание, что топологическая сортировка имеет вид O(n + m).

. Ранее я предоставил реализацию здесь , которую можно легко изменить для этой проблемы.

Answer 3

При условии, что вы можете посчитать количество ребер в / из узла за линейное время, это возможно. Сначала найдите вершины, у которых нет исходящих ребер (O (n) для сканирования всех узлов). Ваши условия выполняются, только если есть только одна такая вершина. Затем посчитайте его входящие ребра (O (n) для сканирования всех входных ребер). Ваши условия выполняются, если есть ровно n-1 входящих ребер. Если какой-либо из тестов не пройден, вершины раковины не будет.

Я предполагаю, что под «соединенным» вы подразумеваете «соединенный ребром», а не «достижимый путем».