Как найти минимальный набор вершин в ориентированном графе, чтобы можно было достичь всех остальных вершин

Question

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

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

Наибольший возможный результат был бы, если бы не было ребер, поэтому все узлы были бы возвращены.

Если на графике есть циклы, для каждого цикла выбирается один узел. Неважно, какой именно, но он должен быть последовательным, если алгоритм будет запущен снова.

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

Учитывая, что мне нужно реализовать это в javascript, предпочтение будет отдано библиотеке .js или примеру кода javascript.

Answer 1

Насколько я понимаю, это просто поиск сильно связанных компонентов в графе. Алгоритм Косараджу - один из самых удачных подходов для этого. Он использует два поиска в глубину по сравнению с некоторыми более поздними алгоритмами, которые используют только один, но мне больше всего нравится его простая концепция.

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

Answer 2

[РЕДАКТИРОВАТЬ # 2: Как упоминает Джейсон Орендорфф в комментарии, поиск набора вершин обратной связи является излишним и будет производить набор вершин больше, чем необходимо в целом. ответ Кюна является (или будет, когда он / она добавит важную информацию в комментариях) правильным способом сделать это.]

[РЕДАКТИРОВАТЬ: я сделал два шага в неправильном направлении ... Теперь мы должны гарантировать минимальность.]

1. Назовите все вершины с нулевым градусом Z. Ни одна вершина в Z не может быть достигнута какой-либо другой вершиной, поэтому она должна быть включена в окончательный набор.
2. Используя обход в глубину (или в ширину), отследите все вершины, доступные из каждой вершины в Z, и удалите их - эти вершины уже "покрыты" Z.
3. График теперь состоит исключительно из направленных циклов. Найдите набор вершин обратной связи F, который дает вам наименьший возможный набор вершин, удаление которых нарушит каждый цикл в графе. К сожалению, как показывает эта ссылка на Википедию, эта проблема сложна для ориентированных графов.
4. Набор вершин, которые вы ищете, Z+F.