Sunday, July 9, 2017

4. Obtain the Topological ordering of vertices in a given graph.

#include<stdio.h>
#include<conio.h>
void main()
{
int a[10][10],t[10],stack[10],indeg[10],n,u,v,i,j,sum=10,top=-1,k=0;
clrscr();
printf("enter the no of vertex\n");
scanf("%d",&n);
printf("enter the adjency matrix\n");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&a[i][j]);
for(i=0;i<n;i++)
indeg[i]=0;
for(j=0;j<n;j++)
{
sum=0;
for(i=0;i<n;i++)
{
sum=sum+a[i][j];
}
indeg[j]=sum;
}
for(i=0;i<n;i++)
{
if(indeg[i]==0)
{
stack[++top]=i;
}
}
while(top!=-1)
{
u=stack[top--];
t[k++]=u;
for(v=0;v<n;v++)
{
if(a[u][v]==1)
{
indeg[v]--;
if(indeg[v]==0)
{
stack[++top]=v;
}
}
}
}
printf("toplog is\n");
for(i=0;i<n;i++)
{
printf("%d\t",t[i]+1);
printf("\n");
}
getch();
}

No comments:

Post a Comment