Scribd
Upload
4 views2 pages

5.topological Ordering

The document provides a C/C++ program that implements a method to obtain the topological ordering of vertices in a directed graph (digraph). It includes a function to sort the graph based on the input adjacency matrix and checks for the possibility of topological ordering. The program outputs either the topological order or indicates that ordering is not possible based on the input graph data.

Uploaded by

Kalaiselvi Subramanian
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
4 views2 pages

5.topological Ordering

The document provides a C/C++ program that implements a method to obtain the topological ordering of vertices in a directed graph (digraph). It includes a function to sort the graph based on the input adjacency matrix and checks for the possibility of topological ordering. The program outputs either the topological order or indicates that ordering is not possible based on the input graph data.

Uploaded by

Kalaiselvi Subramanian
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

5.

Design and implement C/C++ Program to obtain the Topological ordering of vertices in a
given digraph.

PROGRAM:
#include<stdio.h>
#include<conio.h>
inttemp[10],k=0;
void sort(int a[][10],int id[],int n)
{
inti,j;
for(i=1; i<=n; i++)
{
if(id[i]==0)
{
id[i]=-1;
temp[++k]=i;
for(j=1; j<=n; j++)
{
if(a[i][j]==1 && id[j]!=-1)
id[j]--;
}
i=0;
}
}
}
void main()
{
int a[10][10],id[10],n,i,j;
printf("\nEnter the n value:");
scanf("%d",&n);
for(i=1; i<=n; i++)
id[i]=0;
printf("\nEnter the graph data:\n");
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
{
scanf("%d",&a[i][j]);
if(a[i][j]==1)
id[j]++;
}
sort(a,id,n);
if(k!=n)
printf("\nTopological ordering not possible");
else
{
printf("\nTopological ordering is:");
for(i=1; i<=k; i++)
printf("%d ",temp[i]);
}
getch();
}

OUTPUT:
Run 1:
Enter the n value:6
Enter the graph data:
001100
000110
000101
000001
000001
000000
Topological ordering is: 1 2 3 4 5 6

Run 2:
Enter the n value:4

Enter the graph data:


1432
5421
5342
4123
Topological ordering not possible

You might also like