# Topological Sort Algorithm in C++

«
»
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.

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.

1. `/*`
2. ` * C++ Program for Topological Sorting in Graphs`
3. ` */`
4. `#include <iostream>`
5. `#include <conio.h>`
6. `using namespace std;`
7. `struct node_info`
8. `{`
9. `    int no;`
10. `    int lv_time, st_time;`
11. `}*q = NULL, *r = NULL;`
12. `struct node`
13. `{`
14. `    node_info *pt;`
15. `    node *next;`
16. `}*top = NULL, *p = NULL, *np = NULL;`
17. `int c = 0;`
18. `void push(node_info *ptr)`
19. `{`
20. `    np = new node;`
21. `    np->pt = ptr;`
22. `    np->next = NULL;`
23. `    if (top == NULL)`
24. `    {`
25. `        top = np;`
26. `    }`
27. `    else`
28. `    {`
29. `        np->next = top;`
30. `        top = np;`
31. `    }`
32. `}`
33. `node_info *pop()`
34. `{`
35. `    if (top == NULL)`
36. `    {`
37. `        cout<<"underflow\n";`
38. `    }`
39. `    else`
40. `    {`
41. `        p = top;`
42. `        top = top->next;`
43. `        return(p->pt);`
44. `        delete(p);`
45. `    }`
46. `}`
47. `void topo(int *v,int am[],int i)`
48. `{`
49. `    q = new node_info;`
50. `    q->no = i;`
51. `    q->st_time = c;`
52. `    cout<<"start time for node no "<<q->no<<":"<<c<<endl;`
53. `    push(q);`
54. `    v[i] = 1;`
55. `    for (int j = 0; j < 7; j++)`
56. `    {`
57. `        if (am[i][j] == 0 || (am[i][j] == 1 && v[j] == 1))`
58. `            continue;`
59. `        else if(am[i][j] == 1 && v[j] == 0)`
60. `        {`
61. `            c++;`
62. `            topo(v,am,j);`
63. `        }`
64. `    }`
65. `    c++;`
66. `    r = pop();`
67. `    cout<<"leave time for "<<r->no<<":"<<c<<endl;`
68. `    return;`
69. `}`
70. `int main()`
71. `{`
72. `    int v,am;`
73. `    for (int i = 0; i < 7; i++)`
74. `    v[i] = 0;`
75. `    for (int i = 0; i < 7; i++)`
76. `    {`
77. `        cout<<"enter the values for adjacency matrix row:"<<i + 1<<endl;`
78. `        for(int j = 0; j < 7; j++)`
79. `        {`
80. `            cin>>am[i][j];`
81. `        }`
82. `    }`
83. `    topo(v,am,0);`
84. `    getch();`
85. `}`

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

Note: Join free Sanfoundry classes at Telegram or Youtube 