Find articulation vertices in undirected graph by BFS

Question

I have a problem at undirected graphs that sounds like this: "Do a breadth-first traversal of the graph and list the articulation points of the graph.". I found only algorithms that use DFS to find articulation vertices. Is there any way to find those vertices with BFS? Thank you.

Update: How about removing each node, and then doing BFS on the remaining graph? if it covers all nodes, then the deleted node was not an articulation point. I know it's inefficient but i think it's ok.

Answer 1

Not without doing a bunch of extra work.

The reason is that you can't determine whether a point is an articulation point without looking at its children, children of its children, etc to find which ones connect back to the root vertex in some way. A depth first search does that for you automatically. A breadth first search doesn't.

You could simulate it, but only by doing a breadth-first search and then remembering all of the intermediate state for a depth-first search. Which is a lot of overhead for no real gain.