Найти вершины артикуляции в неориентированном графе с помощью BFS

Question

У меня проблема с неориентированными графами, которая звучит так: «Сделайте обход графика в ширину и перечислите точки сочленения графа».Я нашел только алгоритмы, которые используют DFS для поиска вершин артикуляции.Есть ли способ найти эти вершины с помощью BFS?Спасибо.

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

Answer 1

Не без выполнения дополнительной работы.

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

Вы могли бы смоделировать это, но только выполнив поиск в ширину, а затем запомнив все промежуточное состояние для поиска в глубину. Что составляет лот накладных расходов без реальной выгоды.