Algorithm: topological_sort(N, adj[N][N])
T = []
visited = []
in_degree = []
for i = 0 to N
in_degree[i] = visited[i] = 0
for i = 0 to N
for j = 0 to N
if adj[i][j] is TRUE
in_degree[j] = in_degree[j] + 1
for i = 0 to N
if in_degree[i] is 0
enqueue(Queue, i)
visited[i] = TRUE
while Queue is not Empty
vertex = get_front(Queue)
dequeue(Queue)
T.append(vertex)
for j = 0 to N
if adj[vertex][j] is TRUE and visited[j] is FALSE
in_degree[j] = in_degree[j] - 1
if in_degree[j] is 0
enqueue(Queue, j)
visited[j] = TRUE
return T
C program:
#include <stdio.h>
int main(){
int i,j,k,n,a[10][10],indeg[10],flag[10],count=0;
printf("Enter the no of vertices:\n");
scanf("%d",&n);
printf("Enter the adjacency matrix:\n");
for(i=0;i<n;i++){
printf(" vertex %c\n",i+65);
for(j=0;j<n;j++){
printf("connect to vertex %c\n",j+65);
scanf("%d",&a[i][j]);
}
}
for(i=0;i<n;i++){
indeg[i]=0;
flag[i]=0;
}
for(i=0;i<n;i++)
for(j=0;j<n;j++)
indeg[i]=indeg[i]+a[j][i];
printf("\nThe topological order is:");
while(count<n){
for(k=0;k<n;k++){
if((indeg[k]==0) && (flag[k]==0)){
printf("%d ",(k+1));
flag [k]=1;
}
for(i=0;i<n;i++){
if(a[i][k]==1)
indeg[k]--;
}
}
count++;
}
return 0;
}
Output:
Enter the no of vertices:
4
Enter the adjacency matrix:
vertex A
connect to vertex A
0
connect to vertex B
1
connect to vertex C
0
connect to vertex D
0
vertex B
connect to vertex A
0
connect to vertex B
0
connect to vertex C
0
connect to vertex D
1
vertex C
connect to vertex A
0
connect to vertex B
0
connect to vertex C
0
connect to vertex D
0
vertex D
connect to vertex A
1
connect to vertex B
0
connect to vertex C
1
connect to vertex D
0
The topological order is:1 2 3 4
0 comments:
Post a Comment