0
$\begingroup$

So I'm looking at an algorithm for finding bridges in an undirected graph. The thing is, there is a version of this algorithm that I've used so far that looks like this (C++)

     void DFS(int u){
            //link and low link are vectors that hold the link and low link value 
            //for each node,'time' is initialized at zero.
            visited[u] = true;

            link[u] = low_link[u] = time++;


            for(int neighbour: adj[u]){

                if(!visited[neighbour]){
                    parent[neighbour] = u;

                    DFS(neighbour);

                    low_link[u] = min(low_link[u], low_link[neighbour]);
                    if(low_link[neighbour] > link[u]){
                        //found the bridge
                    }


                }else if(neighbour != parent[u]){

                    low_link[u] = min(low_link[u], low_link[neighbour]);
                }

            }



        }

However I've stumbled upon an algorithm that's almost exactly the same as this one except for one small detail. In the else if branch of the first if statement (when determined that the neighbour node is already visited but not the parent of the current node) instead of

low_link[u] = min(low_link[u], low_link[neighbour]);

it does:

low_link[u] = min(low_link[u], link[neighbour])

Or, as I like to figuratively call it, "steals" the neighbour's link instead of stealing its low link. Both algorithms are from very good sources so I can't say for sure that one of them is wrong. However it seems weird to me that both would be right, even though it's such a subtle difference. I've tried illustrating this and seeing whether it makes any difference at all but it's difficult to come up with a good example (whenever I try this on a graph and get to the 'elseif' case the link and the low_link are the same value at that time so both algorithms would essentially do the same). So, any ideas? Thanks.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.