Дилемма подключенных компонентов DFS

Question

Вопрос: Разделите набор вершин графа в Задаче 1 на сильно связанные компоненты (SCC). А именно, укажите, какие вершины находятся в первом сильно связанном компоненте, который во втором и т. Д.

Любой, кто может подтвердить, что это сделано правильно? а именно, когда я достигает вершины 4, у меня есть возможность сделать первый ГТК либо 1,7,2,4,3 (как показано), либо 1,7,2,4,6,5 в зависимости от того, каким образом я выбираю путешествие. Есть ли способ для этого, или я просто могу выбрать?

заказ:

1,2,7,3,4,5,8,6

SCC:

1,7,2, 4,3

Answer 1

Сильно подключен компонент {1,2,3,4,5,6,7}. Если вы этого не сделаете, ваш алгоритм (или ваша реализация) имеет ошибку. Существует определение сильно связанного компонента и нескольких известных алгоритмов; оба могут быть легко найдены в Википедии (и многих других интернет-ресурсах) и, скорее всего, в вашем учебнике и/или курсах. (Если у вас нет заметок по курсу, вы легко найдете их для подобных курсов.)

Answer 2

вы можете добавить 5 и 6 в 1,7,2,4,3, так как оба доступны из других через 4

в ДФС вы должны продолжать visting узел и создания дерева, а стек не пуст , если это так, то restsrt с наименьшим идентификатором, который по-прежнему белый