recent

topological sorting

c program to implement topological sort 
Task -Implement the Topological Sort algorithm. Mention the finishing time of each vertices


header.h
int dfs(int **a,int *visited,int v,int *d,int *f,int time,int s,int *stack);

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


int top=-1;
int dfs(int **a,int *visited,int v,int *d,int *f,int time,int s,int *stack){
int i,j,u;

visited[s]=1;
d[s]=++time;
for(i=0;i<v;i++){

if(a[s][i]==1 && visited[i]==0){
time=dfs(a,visited,v,d,f,time,i,stack);
    }
}
f[s]=++time;
printf("vertex :%d   discovery time:%d    finish time:%d \n",s,d[s],f[s]);  

top++;
stack[top]=s;
return time;
}



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

int stack[100];

int main(){
int **a,i,j,v,*visited,*d,*f,time=0;
FILE *fp;
struct timeval tim;
double time_start,time_end,time1;
fp=fopen("input.txt","r");
fscanf(fp,"%d",&v);

visited=(int *)calloc(v,sizeof(int));
d=(int *)calloc(v,sizeof(int));
f=(int *)calloc(v,sizeof(int));

a=(int **)calloc(v,sizeof(int *));

for(i=0;i<v;i++){
a[i]=(int *)calloc(v,sizeof(int));
}a

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

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

        fscanf(fp,"%d",&a[i][j]);

    }
}
printf("the number of vertex are :%d\n",v);
printf("the adjacency matrix given in the file 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);

printf("the start time and the finish times are :\n");
for(i=0;i<v;i++){
if(visited[i]==0)
dfs(a,visited,v,d,f,time,i,stack);
}

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

printf("the order of topological sort is :\n");
for(i=v-1;i>=0;i--){

if(i==0)
printf("%d\n",stack[i]);

else
printf("%d->",stack[i]);

}
printf("Execution time taken is %1f\n",time1);

return 0;



 topologicalsort.c
#include<stdio.h>
#include<stdlib.h>

int top=-1,stack[100];

int dfs(int **a,int *visited,int v,int *d,int *f,int time,int s){
int i,j,u;

visited[s]=1;
d[s]=++time;

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

if(a[s][i]==1 && visited[i]==0){
time=dfs(a,visited,v,d,f,time,i);
    }

}

f[s]=++time;

top++;
stack[top]=s;

return time;

}

int main(){
int **a,i,j,v,*visited,*d,*f,time=0;
FILE *fp;

//printf("enter the number of vertices");
fp=fopen("input.txt","r");
printf("enter the number of vertices");
fscanf(fp,"%d",&v);

visited=(int *)calloc(v,sizeof(int));
d=(int *)calloc(v,sizeof(int));
f=(int *)calloc(v,sizeof(int));

a=(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]);

    }
}

for(i=0;i<v;i++){
if(visited[i]==0)
dfs(a,visited,v,d,f,time,i);
}

for(i=top;i>=0;i--){

printf("%d->",stack[i]);

}
return 0;



input.txt
5
0 5 0 0 4
5 0 2 3 0
0 2 0 0 0
0 3 0 0 1
4 0 0 1 0


5
0 1 0 0 1
1 0 1 1 0
0 1 0 0 0
0 1 0 0 1
1 0 0 1 0
 

 
Powered by Blogger.