простите за неровный почерк дублирование топика, но тут треды не поднимаются, а мне проект сдавать через неделю на вторую страницу, похоже, заглядывают очень редко. что имеем:
Алгоритм:
1) Нашли точки сочленения
2) Рассматриваем граф без них
3) Сжимаем каждую связную компоненту в вершину
4) Находим минимальное остовное дерево
5) Восстанавливаем по пунктам 2-4, что надо было сделать с исходным графом
Вопрос:
но что делать, если в графе существуют «островки» вершин, не связанные с основным графом? теперь получается так, что при вызове алгоритма при отсутствии точек артикуляции, ничего не происходит; когда же такие точки присутствуют, эти островки становятся соединёнными с основным графом. можно, конечно, отказаться от варианта достраивания уже существующего графа для обеспечения двусвязности и строить только минимальный двусвязный граф, но уж очень хочется, чтобы такая возможность существовала.