recent

Algorithm to find articulation points

c program implementation of Algorithm to find articulation points
 Task- Find and Implement the articulation point in a graph

 header.h
int dfs(int visited[],int s,int v,int **a); 

main.c
#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
#include"header.h"

int main(){

int v,**a,j,i,*visited,flag=0,counter=0;
struct timeval tim;
double time_start,time_end,time1;
FILE *fp;
fp=fopen("input.txt","r");

fscanf(fp,"%d",&v);
a=(int **)calloc(v,sizeof(int *));
visited=(int *)calloc(v,sizeof(int));

for(i=0;i<v;i++){

a[i]=(int *)calloc(v,sizeof(int));

}

for(i=0;i<v;i++){

    for(j=0;j<v;j++){
        fscanf(fp,"%d",&a[i][j]);
    }
}

printf("the adjacency matrix is :\n");
for(i=0;i<v;i++){

    for(j=0;j<v;j++){
        printf("%d ",a[i][j]);
    }
printf("\n");
}

printf("the graph is :\n");
for(i=0;i<v;i++){

    for(j=0;j<v;j++){
        if(a[i][j]==1)
        printf("%d--->%d\n",i,j);
    }
}

gettimeofday(&tim,NULL);
time_start=(double)tim.tv_sec +(double)(tim.tv_usec/1000000.0);


for(i=0;i<v;i++){
flag=0;
counter=0;

for(j=0;j<v;j++){
if(a[i][j]==1){
counter=1;
break;
}
}

if(counter==0){
printf("%d is not an articulation point\n",i);
continue;

}

visited[i]=1;

dfs(visited,j,v,a);

for(j=0;j<v;j++)
{
    if(a[i][j]==1 && visited[j]==0){

    printf("%d is an articulation point\n",i);
    flag=1;
    break;   
    }
}

if(flag==0)
printf("%d is not an articulation point\n",i);

for(j=0;j<v;j++)
visited[j]=0;
}

gettimeofday(&tim,NULL);
time_end=(double)tim.tv_sec +(double)(tim.tv_usec/1000000.0);
time1=time_end-time_start;
printf("Execution time taken is %1f\n",time1);
return 0;
}
 


dfs.c
#include<stdio.h>
#include<stdlib.h>
#include<limits.h>

int dfs(int visited[],int s,int v,int **a){

int stack[v];
int top=-1;
int temp,i;

top++;
stack[top]=s;
visited[s]=1;
while(top!=-1){

temp=stack[top];
top--;

for(i=0;i<v;i++){

if(a[temp][i]>0 && visited[i]==0){
visited[i]=1;
top++;
stack[top]=i;
}
}
}
}


input.txt
4
0 1 0 1
1 0 0 1
0 0 0 1
1 1 1 0
 

 
Powered by Blogger.