9Google AdSense

Find topological sort of directed graph


#include<stdio.h>

int vertex,indegree1[50],strtop[50];
int graph[50][50];
void topo(int vertex);

int main()
{


    int i,j,edge,p,x,y,kk,ff,rr;
    printf("Enter the Number of Vertex : ");
    scanf("%d",&vertex);
    printf("\n");
    printf("Enter the Number of Edge : ");
    scanf("%d",&edge);
    printf("\n");
    for(ff=1;ff<=vertex;ff++)
    for(rr=1;rr<=vertex;rr++)
        graph[ff][rr]=0;
    for(i=1;i<=edge;i++)
    {
    scanf("%d%d",&x,&y);
    graph[x][y]=1;

    }
    for(kk=1;kk<=vertex;kk++)
    {    indegree1[kk]=0;
    strtop[kk]=0;
    }
    printf("\n");
    for(i=1;i<=vertex;i++)
      for(j=1;j<=vertex;j++)
          if(graph[j][i]==1)
            indegree1[i]++;
    topo(vertex);
    return 0;
}
void topo(int vertex)
{
    int l,p,xx,node,top=0,d=0,flag=0,pp;
    for(l=1;l<=vertex;l++)
    {
        if(indegree1[l]==0)
        {
              strtop[++top]=l;
              flag=1;
        }

    }
    if(flag==0)
    {    printf("Topological sort is not possible\n");

    }
    else
    {

        while(d!=vertex)
        {
        node=strtop[++d];
        for(xx=1;xx<=vertex;xx++)
            if(graph[node][xx]==1)
            {
                indegree1[xx]=indegree1[xx]-1;
                if(indegree1[xx]==0)
                    strtop[++top]=xx;
            }


        }
        printf("\nAfter topological sort : \n");
        for(pp=1;pp<=vertex;pp++)
            printf("%d ",strtop[pp]);
        printf("\n");

    }

}

No comments: