Я делаю некоторую практику для предстоящего собеседования, и я нашел практический вопрос, который требует алгоритма O (V + E), чтобы определить, является ли граф двусвязным. На этой странице из Принстона говорится, что граф является двусвязным, если он не имеет вершин артикуляции, где вершина сочленения — это вершина, удаление которой увеличит количество компонент связности (поскольку двусвязный граф должен иметь одну компоненту связности).
Одним из распространенных решений этой проблемы является выполнение DFS с дополнительным отслеживанием, чтобы увидеть, являются ли какие-либо вершины вершинами артикуляции. На этой странице говорится, что вершина вершина сочленения, если
- V является корневым узлом как минимум с двумя дочерними узлами ИЛИ
- У V есть ребенок, который не может связаться с предком V
Однако условие для корневых узлов не имеет для меня смысла. Вот пример двусвязного графа:
Если мы выберем какой-либо из узлов в качестве корня, ВСЕ они будут иметь 2 или более дочерних элементов, поэтому это будет вершина сочленения, что сделает граф не двусвязным. Это обычный алгоритм поиска связных компонентов, поэтому предположим, что я что-то не так понял. Что мне на самом деле нужно проверить для корневого узла, чтобы увидеть, является ли граф двусвязным?