Блог

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

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

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

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

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