Finding articulation point of undirected graph by DFS

Question

I'm trying to implement a program to find the articulation point of an undirected graph using DFS. I'm missing out a basic pointer de-referencing concept to retrieve the adjacency vertex of a given vertex. Kindly rectify the erroneous statement.

#include <stdio.h>
#include <stdlib.h>
#define MIN(X,Y) ((X) < (Y) ?  (X) : (Y))
#define NIL -1

// A structure to represent an adjacency list node
struct AdjListNode
{
  int dest;
  struct AdjListNode* next;
};

// A structure to represent an adjacency list
struct AdjList
{
  struct AdjListNode *head;  // pointer to head node of list
};

// A structure to represent a graph. A graph is an array of adjacency lists.
// Size of array will be V (number of vertices in graph)
struct Graph
{
  int V;
  struct AdjList* array;
};

struct AdjListNode* newAdjListNode(int dest)
{
  struct AdjListNode* newNode = (struct AdjListNode*) malloc(sizeof(struct        AdjListNode));
  newNode->dest = dest;
  newNode->next = NULL;
  return newNode;
}

struct Graph* createGraph(int V)
{
  struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
  graph->V = V;

// Create an array of adjacency lists.  Size of array will be V
  graph->array = (struct AdjList*) malloc(V * sizeof(struct AdjList));

// Initialize each adjacency list as empty by making head as NULL
  int i;
  for (i = 0; i < V; ++i)
    graph->array[i].head = NULL;

  return graph;
}
void addEdge(struct Graph* graph, int src, int dest)
{
// Add an edge from src to dest.  A new node is added to the adjacency
// list of src.  The node is added at the begining
  struct AdjListNode* newNode = newAdjListNode(dest);
  newNode->next = graph->array[src].head;
  graph->array[src].head = newNode;

// Since graph is undirected, add an edge from dest to src also
  newNode = newAdjListNode(src);
  newNode->next = graph->array[dest].head;
  graph->array[dest].head = newNode;
}

int isArticulationPoint(int,int,struct Graph*);
void APUtil(int, int*, int*, int*, int*, int*,struct Graph*);

The main program, including a sample graph.

int main()
{

int V = 9,myNum;
struct Graph* graph = createGraph(V);
addEdge(graph, 0, 4);
addEdge(graph, 0, 2);
addEdge(graph, 0, 3);
addEdge(graph, 1, 2);
addEdge(graph, 1, 4);
addEdge(graph, 1, 7);
addEdge(graph, 1, 8);
addEdge(graph, 3, 4);
addEdge(graph, 3, 5);
addEdge(graph, 5, 6);

scanf("%d",&myNum);

printf("%s",isArticulationPoint(myNum,V,graph)? "Yes" : "No" );

return 0;
}

void APUtil(int u, int visited[], int disc[], 
int low[], int parent[], int ap[],struct Graph* graph)
{
// 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] = 1;

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

// Go through all vertices aadjacent to this
  struct AdjListNode *i;
  for (i = graph->array[u].head; i != NULL; ++i)
  {
    int v = i->dest;  // v is current adjacent of u.Here i'm messed up

    // 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,graph);

        // 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] = 1;

        // (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] = 1;
    }

    // Update low value of u for parent function calls.
    else if (v != parent[u])
        low[u]  =MIN(low[u], disc[v]);
    }
  }
  int isArticulationPoint(int myNum,int V,struct Graph* graph)
  {
// Mark all the vertices as not visited
  int *visited = (int *)malloc(V*sizeof(int));
  int *disc = (int *)malloc(V*sizeof(int));
  int *low = (int *)malloc(V*sizeof(int));
  int *parent = (int *)malloc(V*sizeof(int));
  int *ap = (int *)malloc(V*sizeof(int)); // To store articulation points

// Initialize parent and visited, and ap(articulation point) arrays
  int i;
  for ( i = 0; i < V; i++)
  {
    parent[i] = NIL;
    visited[i] = 0;
    ap[i] = 0;
  }

// Call the recursive helper function to find articulation points
// in DFS tree rooted with vertex 'i'
  for ( i = 0; i < V; i++)
    if (visited[i] == 0)
        APUtil(i, visited, disc, low, parent, ap,graph);

// Now ap[] contains articulation points, return 1 or 0
  if (ap[myNum] == 1)
        return 1;
  else return 0;
 }

Answer 1

It's not easy to make you understand, but look here at my code. I hope you will find what you need.

int min(int a,int b)
{
    return(a<b?a:b);
}
struct node
{
 int val;
 struct node* next;
};
struct graph
{   
 int v;
 struct node** arr;
};
struct graph* createGraph(int v)
{
    int i;
    struct graph* temp =(struct graph*)malloc(sizeof(struct graph));
    temp->v=v;
    for(i=0;i<v;i++)
     temp->arr=(int**)malloc(sizeof(int*)*v);
    for(i=0;i<v;i++)
     temp->arr[i]=NULL;
    return temp;
}
void addEdge(struct graph* g,int u,int v)
{
    struct node* temp =(struct node*)malloc(sizeof(struct node));
    temp->val = v;
    temp->next = g->arr[u];
    g->arr[u] = temp;     
}
void apUtil(struct graph * g,int node,int* isVisited,int* des,int* parent,int* low,int* ap)
{
    struct node* temp=NULL;
    static int time=0;
    int children=0;
    temp = g->arr[node];
    isVisited[node]=1;
    time++;
    //printf("\nsetting time for %d",node);
    des[node]=low[node]=time;

    while(temp!=NULL)
    {       
       if(!isVisited[temp->val])
        {
          children++;
          parent[temp->val]=node;
          apUtil(g,temp->val,isVisited,des,parent,low,ap);

      low[node]= min(low[node],low[temp->val]);

          if(parent[node]==-1 && children>1)
             ap[node]=1;

      if(parent[node]!=-1 && des[node]<=low[temp->val])
            ap[node]=1;           
        }    
        else if(temp->val!=parent[node])
        {
            low[node]=min(low[node],des[temp->val]);
        }
       temp= temp->next;
      }
     //printf("%d",node);
}
void AP(struct graph* g)
{
    int i;
    int* des = (int*)malloc(sizeof(int)*g->v);
    int* isVisited = (int*)malloc(sizeof(int)*g->v);
    int* parent = (int*)malloc(sizeof(int)*g->v);
    int* low = (int*)malloc(sizeof(int)*g->v);
    int* ap = (int*)malloc(sizeof(int)*g->v);
    for(i=0;i<g->v;i++)
    {
        isVisited[i]=0;
        parent[i]=-1;
        ap[i]=0;
    }
    for(i=0;i<g->v;i++)
    {
        if(isVisited[i]==0)
        {
            apUtil(g,i,isVisited,des,parent,low,ap);
        }
    }
    printf("\n");
    for(i=0;i<g->v;i++)
    {
        printf(" %d ",ap[i]);
    }
}
main()
{
    struct graph* g = createGraph(5);
    addEdge(g,1,0);
    addEdge(g,0,2);
    addEdge(g,2,1);
    addEdge(g,0,3);
    addEdge(g,3,4);
    AP(g);
}   

Answer 2

My code running fine,you can try this one

#include <iostream>
#include<bits/stdc++.h>
#include<vector>
#include<utility>
using namespace std;
vector<int>v[1000];
pair<int,int>p[1000];
void dfs(int i,int disc[],int low[],int parent[],bool visit[],int ap[])
{
static int counter=0,k=0;
int child =0;
disc[i]=low[i]=counter++;
visit[i]=true;
for(unsigned int j=0;j<v[i].size();j++)
{
    //int v1=v[i][j];
    if(!visit[v[i][j]])
    {
        child++;
        parent[v[i][j]]=i;
        dfs(v[i][j],disc,low,parent,visit,ap);

        low[i]=min(low[i],low[v[i][j]]);

        if(parent[i]==-1 && child>1)
        {
            ap[i]=1;
        }
        if(parent[i]!=-1 && low[v[i][j]]>=disc[i])
        {
            ap[i]=1;
        }
        if( low[v[i][j]]>disc[i])
        {
           // cout << "u=" << i << " " << "v=" << v[i][j] << endl;

           p[k].first=i;
           p[k].second=v[i][j];
           k++;

        }

    }
    else if(v[i][j]!=parent[i])
    {
        low[i]=min(low[i],disc[v[i][j]]);
    }
}

 }
 int main()
{
   int n,m,a,b;
   cin >> n >> m;
   for(int i=0;i<m;i++)
   {
       cin >> a >> b;
       v[a].push_back(b);
       v[b].push_back(a);
   }
     int disc[n+1];
     int low[n+1];
     int parent[n+1];
     bool visit[n+1];
     int ap[n+1];
     for(int i=0;i<n+1;i++)
    {
       p[i].first=-1;
       p[i].second=-1;
    }
     for(int i=0;i<n+1;i++)
    {
       disc[i]=0;
       low[i]=0;
       parent[i]=-1;
       visit[i]=false;
       ap[i]=0;
    }
    for(int i=0;i<n+1;i++)
    {
       if(visit[i]==false)
     {
          dfs(i,disc,low,parent,visit,ap);
     }
    }

     int cnnt=0,cnnt1=0;
     for(int i=0;i<n+1;i++)
    {
      if(ap[i]==1)
      {
         cnnt++;
       }
    }
      cout << cnnt << endl;
   for(int i=0;i<n+1;i++)
   {
      if(ap[i]==1)
     {
         cout<< i << " " ;
      }
    }
    cout << endl;
    for(int i=0;i<n+1;i++)
   {
       if(p[i].first!=-1&&p[i].second!=-1)
     {
       cnnt1++;       
      }
    }

       cout << cnnt1 << endl;
     for(int i=0;i<cnnt1-1;i++)
    {
       for(int j=0;j<cnnt-i-1;j++)
       {
          if(p[j].first>p[j+1].first)
          {
              int tmp,tmp1;
              tmp=p[j].first;
              tmp1=p[j].second;
              p[j].first=p[j+1].first;
              p[j].second=p[j+1].second;
              p[j+1].first=tmp;
              p[j+1].second=tmp1;
       }
          else if(p[j].first==p[j+1].first && p[j].second>p[j+1].second)
         {
               int tmp2;
               tmp2=p[j].second;
               p[j].second=p[j+1].second;
               p[j+1].second=tmp2;
          }
       }
     }
      for(int i=0;i<cnnt1;i++)
    {

       cout << p[i].first <<" "<< p[i].second << endl;       

     }
        return 0;
    }