adamantium's blog

Finding articulation point in graph using DFS
By adamantium, 10 years ago, In English

How can i find the articulation point in a graph using DFS algorithm ??? Any pseudo code or source code will be helpful for me......

  • Vote: I like it
  • +4
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

http://e-maxx.ru/algo/cutpoints

→ Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it 
inline void dfs(int node){
    bool flag=0;
    int child=0;
    start[node] = ++timer;
    low[node] = start[node];
    foreach(it,V[node]){
        if(!start[*it]){
            dfs(*it);
            ++child;
            low[node] = min(low[node],low[*it]);
            if (low[*it] >= start[node])
                flag = true;
        }
        else
            low[node] = min(low[node],start[*it]);
    }
    if((node==1 && child > 1) || (node != 1 && flag))
        articulation_points.pb(node); //node is an AP.
}
→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

Here is code:

//MAXN = maximum points in the graph
vector<int> g[MAXN];
bool used[MAXN];
int timer, tin[MAXN], fup[MAXN];

void dfs (int v, int p = -1) {
    used[v] = true;
    tin[v] = fup[v] = timer++;
    int children = 0;
    for (size_t i=0; i<g[v].size(); ++i) {
        int to = g[v][i];
        if (to == p)  continue;
        if (used[to])
            fup[v] = min (fup[v], tin[to]);
        else {
            dfs (to, v);
            fup[v] = min (fup[v], fup[to]);
            if (fup[to] >= tin[v] && p != -1)
                //v is articulation point
                ++children;
        }
    }
    if (p == -1 && children > 1)
        //v is articulation point
        }

int main() {
    int n;
    // read n and g 
    timer = 0;
    for (int i=0; i<n; ++i)
        used[i] = false;
    dfs (0);
}
→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone give me the non-recursive implementation of the procedure to find the number of articulation points in a graph?

→ Reply