Есть ли способ найти все вершины, которые являются частью простого цикла в графике в линейном времени?найти все вершины, которые являются частью простого цикла
Я нашел способ сделать это в O (| V | (| V | + | E |)), но задавался вопросом, есть ли способ сделать это быстрее?
Что вы хотите сделать, это удалить все Bridges (то есть ребра, которые отсоединяют компонент при удалении). Статья Википедии дает линейный алгоритм времени для нахождения всех мостов.
Как только все мосты исчезли, каждый узел либо изолирован (имеет степень 0), либо является частью цикла. Выбросьте одинокие узлы, а оставшиеся - нужные вам узлы.
@DavidRicherby Это исправлено. –
Используя DFS (Глубина первого поиска), вы можете выполнить в O (| V | + | E |) время. при внедрении DFS просто сохраняйте запись вертикалей, которые вы отслеживали, со своим родительским узлом, как только вы обнаружите дочерний узел таким же, как родительский узел (что означает завершение цикла), вы можете объявить все узлы от этого родителя до последнего дочернего узла как часть некоторого простого цикла.
Комментарий ниже, если вам нужно больше объяснений.
Это не ** простой цикл **, это просто ** цикл **. Простой цикл не должен содержать никакого другого цикла. –
Это был алгоритм, который я имел в виду, но я думаю, что если бы я нашел вершину, которую посетили, отслеживая всех ее предшественников, я могу иметь | V | круги (круг, который является частью круга, который является частью круга и т. д.).) и для каждого времени O (| V |) для этого отступления. которая суммируется с O (| V | (| V | + | E |)) – Amnon
Мне нравится ответ Бхаввы: но это поможет, если я подробно опишу его.
Обычно, если вы используете DFS, у вас есть посещенный массив, который содержит либо состояние посещения, либо не посетил.
Теперь у
int visited[N];//N is the number of nodes/vertices in graph
Пусть
visited[i] =-1 if i-th vertex is not yet visited
visited[i] = 0 if i-th vertex is being processed
visited[i] = 1 if processing of i-th vertex is done
Таким образом, если вы столкнулись с вершины вместе с ДФС посещаемой значение 0, это означает, что у вас есть cycle.To найти вершины на цикл, используйте предшественника, чтобы сохранить предыдущую вершину в пути.
Хорошо, думаю, у меня есть ответ. при обработке DFS, для каждой вершины v вычисляют низкую (v) (поясняется ниже). затем запустить DFS еще раз и проверить для каждой вершины V:
если низкий (v) = d (v) (где d (v) является расстояние от корня дерева DFS)
! вершина v является частью простого цикла.
* низкая (v) = мин (д (у), д (и), низкий (ш)), где (V, U) является задним краем и ш является дочерним V в Дерево DFS. рассчитанное по времени O (| V | + | E |).
Возможный [дубликат] (http://cs.stackexchange.com/questions/7216/find-the-simple-cycles-in-a-directed-graph)? –
Я не понимаю, о чем именно вы просите. Вам задан простой цикл и нужно найти вершины на нем? Как этот цикл указан? Вам задан граф и нужно отфильтровать любые вершины, не в каком-либо цикле где-нибудь? –
, учитывая граф G = (V, E), найдем группу вершин U, так что каждая вершина u, принадлежащая U, является вершиной на простом цикле – Amnon