минимальное количество узлов, которые пересекают весь граф

Question

Примечание: Вопрос полностью изменен.

На следующем графике мы можем пройти весь граф, если выберем узлы 0 и 2. Я ищу эффективный алгоритм, который возвращает эти два узла. Обратите внимание, что это не проблема покрытия вершин и не проблема доминирующего множества, поскольку нам не нужно выбирать узел 3. Мы говорим, что, если мы выберем узел 0, мы можем перейти к узлу 1 оттуда, и если мы выберем узел 2, мы можем перейти к узлу 3, а затем к узлу 4 оттуда.

Если я использую алгоритм SCC , он находит все вершины как разные SCC, и я не могу никуда перейти:

C:\>project2 ../../input.txt o.txt
Following are strongly connected components in given graph (Each line is a different SCC)
2
4
3
0
1

Answer 1

Если в графе нет цикла, т. Е. Граф является направленным ациклическим графом (DAG), то нам просто нужно посчитать степени для каждого узла. Множество узлов с степенью 0 является обязательным.

Если вы не знакомы с градусом, если есть ребро a-> b , то степень b увеличивается на 1.

Это работает, потому что, если существует ребро a-> b , то есть b имеет степень, это означает, что существует узел a , из которого b достижимо. Поэтому всегда лучше включать в набор узел a вместо b . Узел с нулевой степенью 0 не имеет другого способа посещения, если только мы не начнем с самого узла. Так что он будет включен в набор.

Если на графике есть цикл, мы ищем Сильно Связанные Компоненты (SCC). Затем мы строим новый граф с учетом SCC как одного узла и добавляем ребра из исходного графа, которые соединяют два разных SCC. Новый график будет DAG. Затем мы можем применить вышеописанную процедуру, чтобы найти необходимый набор узлов.