CODEWITHSUNDEEP
algorithmgraph
Spandan
Spandan

Reputation: 2138

Articulation Points In a Graph

I was going through the algorithm explained to find all the Articulation Points in a Graph , given Here.

This is the function which calculates the Art points :

// A recursive function that find articulation points using DFS traversal
// u --> The vertex to be visited next
// visited[] --> keeps tract of visited vertices
// disc[] --> Stores discovery times of visited vertices
// parent[] --> Stores parent vertices in DFS tree
// ap[] --> Store articulation points
void Graph::APUtil(int u, bool visited[], int disc[],
                                      int low[], int parent[], bool ap[])
{
    // A static variable is used for simplicity, we can avoid use of static
    // variable by passing a pointer.
    static int time = 0;

    // Count of children in DFS Tree
    int children = 0;

    // Mark the current node as visited
    visited[u] = true;

    // Initialize discovery time and low value
    disc[u] = low[u] = ++time;

    // Go through all vertices aadjacent to this
    list<int>::iterator i;
    for (i = adj[u].begin(); i != adj[u].end(); ++i)
    {
        int v = *i;  // v is current adjacent of u

        // If v is not visited yet, then make it a child of u
        // in DFS tree and recur for it
        if (!visited[v])
        {
            children++;
            parent[v] = u;
            APUtil(v, visited, disc, low, parent, ap);

            // Check if the subtree rooted with v has a connection to
            // one of the ancestors of u
            low[u]  = min(low[u], low[v]);

            // u is an articulation point in following cases

            // (1) u is root of DFS tree and has two or more chilren.
            if (parent[u] == NIL && children > 1)
               ap[u] = true;

            // (2) If u is not root and low value of one of its child is more
            // than discovery value of u.
            if (parent[u] != NIL && low[v] >= disc[u])
               ap[u] = true;
        }

        // Update low value of u for parent function calls.
        else if (v != parent[u])
            low[u]  = min(low[u], disc[v]);
    }
}

Now i am having bit of Hard time understanding some of lines of this code .

if (parent[u] != NIL && low[v] >= disc[u])
               ap[u] = true;

Does the above statement mean , that since vertex 'v' is direct child of vertex 'u' , if there is some vertex, which is reachable from 'v' or 'v' itself , which was discovered after 'u' , it implies that a back edge is present .

Now the other statement,

else if (v != parent[u])
     low[u]  = min(low[u], disc[v]);

This statement confuses me a lot. Confusion being , why is here , "disc[v]" used instead of "low[v]" ,like the other statement. What i infer is because 'v' here was already discovered , we cant use "low[v]" here because that will essentially mean that we consider the successors of 'v' too ,in our search for back edge from 'u',which is wrong ,as 'v' wont be 'u's child in DFS tree here.

Am i correct in my explanation? Please provide me the right explanation if i am wrong.

Upvotes: 3

Views: 2230

Answers (1)

hello.co
hello.co

Reputation: 756

First let us focus on the meaning of articulation point, It means that the graph split when you remove it.

A simple graph with 3 points connected together: A-B-C

It's obvious that B is articulation point. When we do a deep-first-search from point A, we get disc[A] < disc[B] < disc[C].

low[B] <= disc[C], because there's no paths (not include the path from its parent) for point c to reach the previous visited point, thus point B is a articulation.

From parent[u] != NIL, we can see the first one is an exception, because there's no previous point before it.

Upvotes: 3

Related Questions