Ytukyg

How can we find all bridges and articulation points using DFS? Suppose we have the following DFS psuedocode (from Wikipedia):

procedure DFS-iterative(G,v):

      let S be a stack

      S.push(v)

      while S is not empty

            v ← S.pop() 

            if v is not labeled as discovered:

                label v as discovered

                for all edges from v to w in G.adjacentEdges(v) do

                    S.push(w)

Are there any simple modifications that can be mode such that when a node is completely discovered, we can fully determine whether the node and it's parent form a bridge and whether the node itself is an articulation point? I guess my first question is how we determine when a node is fully discovered (at what point in the algorithm will we know that the node does not need to be explored further)?

Quite late answer to the question, but let's do this.

Now, you asked for simple modifications to dfs to find bridges and articulation points, are such, there are better ways to do this (Although probably of the same order) that give you more info about the graph, but the following will focus on being a simple change from a normal dfs to find them. At last, some of this wont work if your graph has multiple edges from a node to another (as making it work for these cases would probably kill the simplicity).

Ok, let's start with some modifications we'll make to our dfs, to gather more info about each node, we'll add an array or tag to it named depth. As such, everytime we visit a node, we'll assign it a depth.

Some more info we'll need is an array that will tell us how low (or how high, if you're picturing the tree) you can go, this array will be named "low". The low array will tell us the lowest depth a node can go following a single back-edge (An edge to an already visited node which is not your direct parent).

Having these two things, it's trivial to note that for a node "X" with an edge to "Y", the edge that joins them is a bridge if and only if low[Y] > depth[X], that is, Y cannot go to a node that is on a depth lower than X (that is, higher in the tree formed by the dfs) without passing through the edge that joins them.

Also trivial to notice that for a node "X", if any of his "sons" i (The nodes he visits in the DFS) have a low[i] >= depth[x], then X is an articulation point, because this i couldnt reach any of the ancestors of X without X. there is however an exception for the root, if the root has more than 2 sons, it will also be an articulation point.

Here is a quick pseudocode implementing a recursive version of this.

Let low,depth,parent be arrays initialized in -1

let bridges be a set of edges.

let artPoints be a set of nodes.

dfs(int curr, int d) //curr for current

    low[curr] = d;

    depth[curr] = d;

    d++;

    //We'll increment d here to increase the depth.

    for node adyacent to curr

        if (depth[node] == -1): // node is not visited

            parent[node] = curr;

            dfs(node,d);

            low[curr] = min(low[curr],low[node]);

            // If it's an articulation point, we'll add it.

            if low[node] >= depth[curr]

                artPoints.add(curr)

        // We make sure that the node we're (re)visiting is not our parent            

        else if parent[node] != curr

            low[curr] = min(low[curr],depth[node]); //back-edge



        // If it's a bridge, we'll add it to our bridges list.

        if low[node] > depth[curr]

            bridges.add(pair(curr,node))