Самый быстрый способ определить, будет ли прямоугольный граф разделен, если узел удален

Question

Я работаю над атмосферным симулятором для видеоигры, и проблема, с которой я столкнулся, заключается в том, что мне нужен дешевый (во время обработки) способ, чтобы определить, является ли граф узлов в прямоугольной сетке (каждый узел подключен до четыре соседа, NSEW) стали бы разделены, если бы я удалил определенный узел.

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

Если это возможно, было бы очень и очень желательно избежать поиска по всему графику.

Answer 1

Вы можете найти точки сочленения, используя сначала измененный поиск по глубине - см. http://en.wikipedia.org/wiki/Biconnected_component. Точка сочленения графа - это узел, который в случае удаления отключает граф. Каждый граф можно разбить в точках сочленения на двусвязные компоненты. Если вам повезет, вам просто нужно знать, является ли точка точкой сочленения. Если нет, то, возможно, поможет разбиение графа на дерево двусвязных компонентов и их анализ.