I need this for a game I'm writing in golang.
I've got a bunch of nodes, each containing lists of other nodes, such that there exists a path between any two nodes.
(in fact the objects are rectangles of various sizes tiled together)
I need to test each node to see if, by its destruction, there would remain a path between any two of the remaining nodes, or if some would become unreachable.
(i.e. would the loss of a given rectangle result in two unconnected tiled regions, or would it remain a single tiled region)
I'm hoping a way to perform this test as efficiently as possible, because my code will have to perform this test one many different sets of nodes, as many times as possible, as part of descending into an alphabeta game-tree engine.
Many thanks for any help!
There's a linear time algorithm to find the biconnected components of a graph. The articulation nodes are the ones whose removal would disconnect the graph.