CODEWITHSUNDEEP
algorithmdata-structures
RajGopalbh4
RajGopalbh4

Reputation: 139

Biconnected component

I have read this wonderful algorithm for finding the articulation points in a connected graph https://en.wikipedia.org/wiki/Biconnected_component

In the algorithm lowpoint is calculated for every node which means the lowest depth of neighbors of all descendants of given node .

How does this low point helps to find the articulation point and why it should be calculated ? Especially the non root nodes . I want the significance of lowpoint in the algorithm .

Upvotes: 3

Views: 294

Answers (1)

Yola
Yola

Reputation: 19033

I give two explanations:

  1. Basically, low of vertex V1 is depth of another vertex to which you can get if DFS further from V1, and if you can't get back to any vertex which was discovered prior to V1, then removing V1 would split the graph.

  2. Observe, that if after visiting all vertex children you haven't found a child with smaller low point than the vertex has that means that there is no cycling edges and removing this vertex would split the graph.

enter image description here

Upvotes: 3

Related Questions