Как узнать, является ли неориентированный граф Biconnected или не использует его глубину при первом поисковом обходе.Есть ли другой способ, кроме как обойти весь граф, чтобы найти несвязные части графа.
Вы вычисляете low(v) для каждой вершины в линейном времени (т.е. во время выполнения DFS). И существует мост (то есть ребро, удаление которого будет разъединять граф ==> не двусвязным), если есть некорневая вершина, значение которой low само равно ИЛИ, если корень имеет более одного дочернего элемента.
low(v)
low
Это объяснено здесь в пункте 5.2 http://www.cse.ohio -state.edu / ~ lai / 780 / graph.pdf
У меня нет ответа на этот вопрос, но мое внутреннее чувство подсказывает, что вам придется сначала выполнить поиск в глубину, поскольку двусвязное свойство графа является свойством всего графа, а не его подмножества.