Scribd
Upload
3 views3 pages

LabProgram 5

The document provides a C/C++ program for obtaining the topological ordering of vertices in a directed graph using an adjacency matrix. It includes user input for the number of vertices and the adjacency matrix, followed by a function to perform the topological sorting. The program outputs whether topological ordering is possible and displays the ordering if it is.

Uploaded by

vigguviggu33
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
3 views3 pages

LabProgram 5

The document provides a C/C++ program for obtaining the topological ordering of vertices in a directed graph using an adjacency matrix. It includes user input for the number of vertices and the adjacency matrix, followed by a function to perform the topological sorting. The program outputs whether topological ordering is possible and displays the ordering if it is.

Uploaded by

vigguviggu33
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.

#include<stdio.h>
void topo( );
int ad[10][10], i, j, n, k;
void main( )
{
printf("\n\n********** TOPOLOGICAL SORTING *********\n\n");
printf("Enter the number of vertices\n");
scanf("%d", &n);
printf("\n\nEnter the adjacency matrix\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
scanf("%d", &ad[i][j]);
}
}
printf("\n\nThe entered adjacency matrix is\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("%d\t", ad[i][j]);
}
printf("\n");
}
topo( );
}
void topo( ) //function definition
{
int v[10], in=1, flag=0, count=0, f=1;
while(f) //checking for all possibilities
{
count++;
for(i=1;i<=n;i++)
{
flag = 0;
for(j=1; j<=n; j++)
{
if(ad[j][i] != 0 || v[j]==i)//if there is no incoming edge or if the node is already visited
{
flag = 1;
break;
}
}
if(flag != 1)
{
v[in++] = i;
for(k=1; k<=n; k++)
ad[i][k] = 0;
}
}
if(count == n)
f = 0;
}
if(in < n)
printf("\n\nTopological ordering is not possible\n");
else
{
printf("\n\nTopological ordering is possible\n");
printf("\nOrdering is:\t");
for(i=1; i<=n; i++)
printf("%d\t", v[i]);
}
printf("\n**********************************************");
}

Check the output for the following cases. Draw the graph for the adjacency matrix.

You might also like