Topological Sort

Topological Sort

Definition

Topologic sorting for directed acyclic graph (DAG) is a linear ordering of vertices such that every directed edge uv, vertex u comes before v in ordering.

Algorithm:

Following are the steps to be followed in this algorithm -

1. From a given graph find a vertex with no incoming edges. Delete it along with all the edges outgoing from it. If there are more than one such vertices then break the tie randomly.

2. Note the vertices that are deleted.

3. All these recorded vertices give topologically sorted list.

Let us understand this algorithm with some examples -

Ex. 5.9.1 Sort the digraph for topological sort.

Hence the list after topological sorting will be B, A, D, C, E.

Ex. 5.9.2 Sort the given digraph using topological sort.

Thus the topologically sorted list is B, A, C, D, E.

Ex. 5.9.3 Consider a directed acyclic graph 'D' given in following figure. Sort the nodes of 'D' by applying topological sort on 'D'.

Thus the topological sorting will be A, B, C, G, D, E,F.

Ex. 5.9.4 Implementation of Topological Sort(Application of Graph)

Sol. :

#include<stdio.h>

#define SIZE 10

#define MAX 10

using namespace std;

int G[SIZE][SIZE], i, j, k;

int front, rear;

int n, edges;

int b[SIZE], Q[SIZE], indegree[SIZE];

int create()

{

front = -1; rear = -1;

for (i=0; i<MAX; i++) //initialising the graph

{

for (j = 0; j<MAX; j++)

{

G[i][j] = 0;

}

}

for (i=0; i<MAX; i++)

{

indegree[i] = -99;

}

n = 5;

edges=7;

G[0][2]=1;

G[0][3]=1;

G[1][0]=1;

G[1][3]=1;

G[2][4]=1

G[3][2]=1

G[3][4]=1

return n;

}

void Display(int n)

{

int V1, V2;

for (V1= 0; V1<n; V1++)

{

for (V2= 0; V2<n; V2++)

printf("%d", G[V1][V2]);

printf("\n");

}

}

void Insert_Q(int vertex, int n)

{

if (rear == n)

printf("Queue Overflow\n");

else

{

if (front == -1)/*Empty Queue condition*/

front =0;

rear rear + 1;

Q[rear]=vertex;/* Inserting node into the Q*/

}

}

int Delete_Q()

{

int item;

if (front==-1| | front > rear)

{

printf("Queue Underflow\n");

return -1;

}

else

{

item=Q[front];

front = front + 1;

return item;

}

}

int Compute_Indeg(int node, int n)

{

int v1, indeg_count=0;

for (v1 = 0; v1<n; v1++)

if (G[v1][node] == 1)//checking for incoming edge

indeg_count++;

return indeg_count++;

}

void Topo_ordering(int n)

{

j = 0;

for (i=0; i<n; i++)

{

indegree[i] = Compute_Indeg(i, n);

if (indegree[i]==0)

Insert_Q(i, n);

}

while (front <= rear)

{

k = Delete_Q();

b[j++] = k;

for (i=0; i<n; i++)

{

if (G[k][i]==1)

{

G[k][i] = 0;

indegree[i]=indegree[i] - 1;

if (indegree[i]==0)

Insert_Q(i, n);

}

}

}

printf("\nThe result of after topological sorting is ...");

for (i=0; i<n; i++)

printf("%d",b[i]);

printf("\n");

}

int main()

{

n = create();

printf("The adjacency matrix is : \n");

Display(n);

Topo_ordering(n);

return 0;

}

Output

The adjacency matrix is :

00110

10010

00001

00101

00000

The result of after topological sorting is... 1 0 3 2 4

Review Questions

1. Explain the topological sorting algorithm.

2. State and explain topological sort with suitable example.