0
$\begingroup$

let, low[] and disc[] be two 1D arrays

disc[i] stores the discovery time of node[I]

low[i] stores the lowest value between disc[i] and discovery time of children of node[i]

I'm curious that what is difference between low[u] = Math.min(low[u], disc[v]); and low[u] = Math.min(low[u], low[v]);

why is later incorrect?

The following is the code for finding the bridges in a graph.

    private static void dfs(int u, List<Integer>[] g, boolean[] visited, int[] parent, int[] low,
            int[] disc, List<String> bridges) {
        visited[u] = true;
        disc[u] = low[u] = ++time;

        if(g[u] != null)
            for (int v : g[u]) {
                if(visited[v] && parent[u] != v)
                    low[u] = Math.min(low[u], disc[v]);
                if(!visited[v]){
                    parent[v] = u;
                    dfs(v, g, visited, parent, low, disc, bridges);
                    low[u] = Math.min(low[u], low[v]);
                    if(low[v] > disc[u])
                        bridges.add(String.format("%d -> %d",u,v));
                }
            }        
    }
```
$\endgroup$
  • $\begingroup$ We're not a coding site. Asking us to explain code to you is probably not a good fit here. Any community votes? P.S. Have you tried running both versions of the code on many randomly generated graphs to look for one where they give different results? $\endgroup$ – D.W. Apr 2 at 19:26
  • $\begingroup$ Have you tried running both versions of the code on many randomly generated graphs to look for one where they give different results? no. I was thinking about it. $\endgroup$ – vivek gupta Apr 2 at 19:38
  • 1
    $\begingroup$ Have you read the original paper "Depth-First Search and Linear Graph Algorithms" by Tarjan? I think that it represents this topic better than any other resource available in internet. $\endgroup$ – Laakeri Apr 2 at 19:47
  • $\begingroup$ Thanks, @Laakeri for recommending me this beautiful paper. $\endgroup$ – vivek gupta Apr 2 at 20:00

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.