Biconnected components & Articulation points
#include<stdio.h>
#include<stdlib.h>
#define max 20
typedef struct
{ int u,v;
}edge;
int dfn[max],l[max],num=1,n;
int a[max][max];
edge stack[max];
int top=-1;
void push(edge e)
{
if(top==max-1)
printf("Stack is full");
else
stack[++top]=e;
}
edge pop()
{ edge e;
if(top==-1)
printf("stack is empty");
else
e=stack[top--];
return e;
}
void bicomp(int u,int v)
{ int w;
edge e;
dfn[u]=num;l[u]=num;num++;
for(w=1;w<=n;w++)
if(a[u][w]==1)
{ if((v!=w) && (dfn[w]<dfn[u]))
{ e.u=u; e.v=w;
printf("\nEdge %d -- %d is pushed to stack",e.u,e.v);
push(e);
}
if(dfn[w]==0)
{ bicomp(w,u);
printf("push2");
l[u]=(l[u]<l[w])?l[u]:l[w];
if(l[w]>=dfn[u])
{
printf("\n New Bicomponent for Articulation point %d:",u);
do
{ e=pop();
printf("%d--%d ",e.u,e.v);
}while(!((e.u==u && e.v==w)||(e.u==w && e.v==u)));
}
}
else
if(w!=v)
l[u]=(l[u]<dfn[w])?l[u]:dfn[w] ;
}
}
int main()
{ int i,j;
printf("enter the no. of nodes in a given graph");
scanf("%d",&n);
printf("Enter the adjacency matrix of Graph G with %d vertices",n);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d", &a[i][j]);
printf("The adjacency matrix of Graph G is:\n");
for(i=1;i<=n; printf("\n"),i++)
for(j=1;j<=n;j++)
printf("%d\t", a[i][j]);
printf("The biconnected components of given graph are:\n");
bicomp(1,0);
return 0;
}
#include<stdlib.h>
#define max 20
typedef struct
{ int u,v;
}edge;
int dfn[max],l[max],num=1,n;
int a[max][max];
edge stack[max];
int top=-1;
void push(edge e)
{
if(top==max-1)
printf("Stack is full");
else
stack[++top]=e;
}
edge pop()
{ edge e;
if(top==-1)
printf("stack is empty");
else
e=stack[top--];
return e;
}
void bicomp(int u,int v)
{ int w;
edge e;
dfn[u]=num;l[u]=num;num++;
for(w=1;w<=n;w++)
if(a[u][w]==1)
{ if((v!=w) && (dfn[w]<dfn[u]))
{ e.u=u; e.v=w;
printf("\nEdge %d -- %d is pushed to stack",e.u,e.v);
push(e);
}
if(dfn[w]==0)
{ bicomp(w,u);
printf("push2");
l[u]=(l[u]<l[w])?l[u]:l[w];
if(l[w]>=dfn[u])
{
printf("\n New Bicomponent for Articulation point %d:",u);
do
{ e=pop();
printf("%d--%d ",e.u,e.v);
}while(!((e.u==u && e.v==w)||(e.u==w && e.v==u)));
}
}
else
if(w!=v)
l[u]=(l[u]<dfn[w])?l[u]:dfn[w]
}
}
int main()
{ int i,j;
printf("enter the no. of nodes in a given graph");
scanf("%d",&n);
printf("Enter the adjacency matrix of Graph G with %d vertices",n);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d", &a[i][j]);
printf("The adjacency matrix of Graph G is:\n");
for(i=1;i<=n; printf("\n"),i++)
for(j=1;j<=n;j++)
printf("%d\t", a[i][j]);
printf("The biconnected components of given graph are:\n");
bicomp(1,0);
return 0;
}
Comments
Post a Comment