Что такое быстрый алгоритм поиска критических узлов?

Question

Я ищу быстрый метод / алгоритм для определения того, какие узлы на графике являются критическими.

Например, на этом графике:

Узлы № 2 и 5критически важны.

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

Как лучше?

Answer 1

См. двусвязные компоненты .Называя их точками артикуляции вместо критических узлов, можно получить лучшие результаты поиска.

В любом случае алгоритм состоит из простого поиска в глубину , в котором вы сохраняете определенную информацию для каждого узла.

Answer 2

есть несколько лучших способов. исследование всегда полезно

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

подсказка: как можно украсить графикчтобы сказать вам, какие узлы зависят от каких других узлов, и будет ли эта информация полезна для определения критических узлов?