Достижимые вершины друг от друга

Question

Для заданного графа мне нужно найти все вершины v, такие, что, если u достижима из v, то v также достижима из u. Я знаю, что вершину можно найти с помощью BFS или DFS, но она кажется неэффективной. Мне было интересно, есть ли лучшее решение для этой проблемы. Любая помощь будет оценена по достоинству.

Answer 1

По сути, вы не собираетесь делать ничего лучше, чем какой-либо поиск (как вы указали). Я бы не стал слишком беспокоиться об эффективности: эти алгоритмы, как правило, линейны по числу узлов + ребер.

Проблема немного недоопределенный, так что я буду делать некоторые предположения о вашей структуре данных:

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

В этом случае используйте удобный поиск, начиная с вершины u (глубина/ширина, не имеет значения) дважды: один раз после исходящих ребер (маркировка узлов как «достижимая от u») и один раз после входящих границ (маркировка узлов как «достижение u»). Наконец, итерация по всем узлам и сравнение двух бит в соответствии с вашей целью.

Примечание: в соответствии с вашим набором результатов все узлы, которые не достигают вершины u. Если вы предполагали соединение вместо импликации, вы можете сэкономить немного времени, включив тест во второй поиск, вместо того, чтобы сканировать все узлы на графике. Это также снимает предположение 3.