Finding articulation points using DFS and the bi-components algorithm

1
votes

I am having trouble implementing (not code) DFS incorporating the bi-components algorithm to find articulation points in a graph, the algorithm was presented in my computer science lecture and I didn't grasp the implementation. (Just to clarify I know how to implement DFS) Let me explain: we are given a graph and we have to perform a DFS to find all the articulation points, using back numbers and the DFS number. My major problem is finding the back number of each node, using the given algorithm.

We were given a tutorial as an exercise to implement the algorithm, I done it but I have no idea if it is correct. Could someone please check that I have done it correctly and if possible correct me. The tutorial question is as follows

Use the algorithm done in class to do a depth-first search tree of the algorithm. For each vertex find:

• the dfs-number

• the back number

• whether it is an articulation point enter image description here The algorithm and My solution is: enter image description here Thanks. Hope someone can help

1
algorithmtheorydepth-first-search
Why do you think that J should be an articulation point? It isn't one. B is not an articulation point either. - kraskevich
Because according to the articulation point condition 15>14, thus it is an articulation point, however I know this is not true because if we remove J, it doesn't disconnect the graph - amine
You have dfs-time = 14 and back-number=12. It's not articulation point according to your algorithm and it's not an articulation point indeed. - kraskevich
Yes I see my error over there - amine

1 Answers

0
votes

You algorithm is almost correct. The only case which is handled improperly is the root: a root is an articulation point if and only if it has two or more children in the dfs tree.