C++ Program to Create a Random Linear Extension for a DAG

This is a C++ Program to find random linear extension of DAG. Linear extension is another term for finding topological sort of a graph.

Here is source code of the C++ Program to Create a Random Linear Extension for a DAG. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

1. `// A C++ program to print topological sorting of a DAG`
2. `#include<iostream>`
3. `#include <list>`
4. `#include <stack>`
5. `using namespace std;`
6. ` `
7. `// Class to represent a graph`
8. `class Graph`
9. `{`
10. `        int V; // No. of vertices'`
11. ` `
12. `        // Pointer to an array containing adjacency listsList`
13. `        list<int> *adj;`
14. ` `
15. `        // A function used by topologicalSort`
16. `        void topologicalSortUtil(int v, bool visited[], stack<int> &Stack);`
17. `    public:`
18. `        Graph(int V); // Constructor`
19. ` `
20. `        // function to add an edge to graph`
21. `        void addEdge(int v, int w);`
22. ` `
23. `        // prints a Topological Sort of the complete graph`
24. `        void topologicalSort();`
25. `};`
26. ` `
27. `Graph::Graph(int V)`
28. `{`
29. `    this->V = V;`
30. `    adj = new list<int> [V];`
31. `}`
32. ` `
33. `void Graph::addEdge(int v, int w)`
34. `{`
35. `    adj[v].push_back(w); // Add w to v’s list.`
36. `}`
37. ` `
38. `// A recursive function used by topologicalSort`
39. `void Graph::topologicalSortUtil(int v, bool visited[], stack<int> &Stack)`
40. `{`
41. `    // Mark the current node as visited.`
42. `    visited[v] = true;`
43. ` `
44. `    // Recur for all the vertices adjacent to this vertex`
45. `    list<int>::iterator i;`
46. `    for (i = adj[v].begin(); i != adj[v].end(); ++i)`
47. `        if (!visited[*i])`
48. `            topologicalSortUtil(*i, visited, Stack);`
49. ` `
50. `    // Push current vertex to stack which stores result`
51. `    Stack.push(v);`
52. `}`
53. ` `
54. `// The function to do Topological Sort. It uses recursive topologicalSortUtil()`
55. `void Graph::topologicalSort()`
56. `{`
57. `    stack<int> Stack;`
58. ` `
59. `    // Mark all the vertices as not visited`
60. `    bool *visited = new bool[V];`
61. `    for (int i = 0; i < V; i++)`
62. `        visited[i] = false;`
63. ` `
64. `    // Call the recursive helper function to store Topological Sort`
65. `    // starting from all vertices one by one`
66. `    for (int i = 0; i < V; i++)`
67. `        if (visited[i] == false)`
68. `            topologicalSortUtil(i, visited, Stack);`
69. ` `
70. `    // Print contents of stack`
71. `    while (Stack.empty() == false)`
72. `    {`
73. `        cout << Stack.top() << " ";`
74. `        Stack.pop();`
75. `    }`
76. `}`
77. ` `
78. `// Driver program to test above functions`
79. `int main()`
80. `{`
81. `    // Create a graph given in the above diagram`
82. `    Graph g(6);`
83. `    g.addEdge(5, 2);`
84. `    g.addEdge(5, 0);`
85. `    g.addEdge(4, 0);`
86. `    g.addEdge(4, 1);`
87. `    g.addEdge(2, 3);`
88. `    g.addEdge(3, 0);`
89. ` `
90. `    cout << "Following is a Topological Sort of the given graph \n";`
91. `    g.topologicalSort();`
92. ` `
93. `    return 0;`
94. `}`

Output:

```\$ g++ RandomLinearExtensionOfDAG.cpp
\$ a.out

Following is a Topological Sort of the given graph
5 4 2 3 1 0
------------------
(program exited with code: 0)

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

Here’s the list of Best Books in C++ Programming, Data Structures and Algorithms.

If you find any mistake above, kindly email to [email protected]

Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!