У меня возникла проблема с реализацией (не кодом) DFS, включающей алгоритм двухкомпонентных алгоритмов, чтобы найти точки сочленения на графике, алгоритм был представлен в моей лекции по информатике, и я не сделал не поймите реализацию. (Просто уточнить, я знаю, как реализовать DFS). Позвольте мне объяснить: нам дается график, и нам нужно выполнить DFS, чтобы найти все точки сочленения, используя обратные номера и номер DFS. Моя главная проблема - найти обратный номер каждого узла, используя данный алгоритм.Поиск точек сочленения с использованием DFS и алгоритма бикомпонентов
Мы получили учебное пособие как упражнение для реализации алгоритма, я это сделал, но я понятия не имею, правильно ли оно. Может кто-то, пожалуйста, проверьте, что я сделал это правильно и, если возможно, исправлю меня. Задача состоит в следующем:
Использовать алгоритм, выполненный в классе, для создания дерева поиска по глубине . Для каждой вершины найти:
• ДФС-номера
• заднее числа
• является ли точкой сочленения
Алгоритм и мое решение:
Спасибо. Надеюсь, кто-то может помочь
Почему вы думаете, что J должен быть точкой артикуляции? Это не одно. B также не является точкой сочленения. – kraskevich
Поскольку в соответствии с условием точки сочленения 15> 14, таким образом, это точка сочленения, однако я знаю, что это неверно, потому что, если мы удалим J, он не отключит график – amine
У вас есть dfs-time = 14 и back- число = 12. Это не точка артикуляции в соответствии с вашим алгоритмом, и это не точка артикуляции. – kraskevich