This C++ program, using an adjacency matrix, displays the times at which the different times at which nodes are visited and left thereby producing a linear ordering of vertices in a graph.

A graph is a set of nodes connected by edges.

A graph is a set of nodes connected by edges.

Here is the source code of the C++ program to display topological sort. The C++ program is successfully compiled and run on DevCpp, a C++ compiler. The program output is also shown below.

`/*`

`* C++ Program for Topological Sorting in Graphs`

`*/`

`#include <iostream>`

`#include <conio.h>`

using namespace std;

`struct node_info`

`{`

int no;

int lv_time, st_time;

}*q = NULL, *r = NULL;

`struct node`

`{`

node_info *pt;

node *next;

}*top = NULL, *p = NULL, *np = NULL;

int c = 0;

void push(node_info *ptr)

`{`

np = new node;

np->pt = ptr;

np->next = NULL;

if (top == NULL)

`{`

top = np;

`}`

`else`

`{`

np->next = top;

top = np;

`}`

`}`

node_info *pop()

`{`

if (top == NULL)

`{`

cout<<"underflow\n";

`}`

`else`

`{`

p = top;

top = top->next;

return(p->pt);

delete(p);

`}`

`}`

void topo(int *v,int am[][7],int i)

`{`

q = new node_info;

q->no = i;

q->st_time = c;

cout<<"start time for node no "<<q->no<<":"<<c<<endl;

push(q);

v[i] = 1;

for (int j = 0; j < 7; j++)

`{`

if (am[i][j] == 0 || (am[i][j] == 1 && v[j] == 1))

continue;

else if(am[i][j] == 1 && v[j] == 0)

`{`

c++;

topo(v,am,j);

`}`

`}`

c++;

r = pop();

cout<<"leave time for "<<r->no<<":"<<c<<endl;

return;

`}`

int main()

`{`

int v[7],am[7][7];

for (int i = 0; i < 7; i++)

v[i] = 0;

for (int i = 0; i < 7; i++)

`{`

cout<<"enter the values for adjacency matrix row:"<<i + 1<<endl;

for(int j = 0; j < 7; j++)

`{`

cin>>am[i][j];

`}`

`}`

topo(v,am,0);

getch();

`}`

Output enter the values for adjacency matrix row:1 0 1 1 0 0 1 1 enter the values for adjacency matrix row:2 1 0 0 0 0 0 0 enter the values for adjacency matrix row:3 1 0 0 0 0 0 1 enter the values for adjacency matrix row:4 0 0 0 0 1 1 0 enter the values for adjacency matrix row:5 0 0 0 1 0 1 1 enter the values for adjacency matrix row:6 1 0 0 1 1 0 0 enter the values for adjacency matrix row:7 1 0 1 0 1 0 0 start time for node no 0:0 start time for node no 1:1 leave time for node no 1:2 start time for node no 2:3 start time for node no 6:4 start time for node no 4:5 start time for node no 3:6 start time for node no 5:7 leave time for node no 5:8 leave time for node no 3:9 leave time for node no 4:10 leave time for node no 6:11 leave time for node no 2:12 leave time for node no 0:13

**Sanfoundry Global Education & Learning Series – 1000 C++ Programs.**

If you wish to look at all C++ Programming examples, go to C++ Programs.