# Algorithm to determine which vertices/edges would disconnect undirected graph if removed

Is anyone aware of an algorithm to determine which vertices/edges would disconnect an undirected graph if removed? For all vertices/edges.

Of course I could run a BFS for each vertex and for each edge to test if the remaining graph would be connected. But is there anything more efficient?

In the end I would like to uniformly draw a vertex/edge out of those that would not disconnect the graph, to make simulations for fail-over routing in a computer network.

For vertices you could use articulation point algorithm that uses DFS and runs in $O(|V| + |E|)$ time. Similarly you could find bridges. Look here and here. But if there is no bridge and you are interested in cut-set (of edges) I guess you could use maximum flow minimum cut algorithm by assigning weight equal to 1 to each edge if they are not weighted. And finally if you are interested in subgraphs whose vertices are connected with each other (there is a path between each pair of vertices) then use an algorithm for computing strongly connected components.
• Thanks, articulation points and bridges are what I was looking for. The Boost Graph Library contains an implementation to find articulation points and biconneted components in $O(|V|+|E|)$. It can also be used to find brides: an edge is a bridge exactly if it is the only edge in a biconnected component. – xblax Jul 17 '17 at 15:14