{"id":26024,"date":"2017-10-26T09:56:11","date_gmt":"2017-10-26T04:26:11","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26024"},"modified":"2017-10-26T09:59:36","modified_gmt":"2017-10-26T04:29:36","slug":"topological-sorting","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/topological-sorting\/","title":{"rendered":"C++ Algorithm – Topological Sorting"},"content":{"rendered":"

Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering. <\/span>Topological Sorting for a graph is not possible if the graph is not a DAG.<\/p>\n

For example, a topological sorting of the following graph is \u201c5 4 2 3 1 0\u201d. There can be more than one topological sorting for a graph. For example, another topological sorting of the following graph is \u201c4 5 2 3 1 0\u201d. The first vertex in topological sorting is always a vertex with in-degree as 0 (a vertex with no in-coming edges)<\/p>\n

Topological Sorting vs Depth First Traversal (DFS)<\/em><\/strong>:
\nIn DFS, we print a vertex and then recursively call DFS for its adjacent vertices. In topological sorting, we need to print a vertex before its adjacent vertices. For example, in the given graph, the vertex \u20185\u2019 should be printed before vertex \u20180\u2019, but unlike DFS, the vertex \u20184\u2019 should also be printed before vertex \u20180\u2019. So Topological sorting is different from DFS. For example, a DFS of the shown graph is \u201c5 2 3 1 0 4\u201d, but it is not a topological sorting<\/p>\n

Algorithm to find Topological Sorting:<\/em><\/strong>
\nWe recommend to first see implementation of DFS here. We can modify DFS to find Topological Sorting of a graph. In DFS, we start from a vertex, we first print it and then recursively call DFS for its adjacent vertices. In topological sorting, we use a temporary stack. We don\u2019t print the vertex immediately, we first recursively call topological sorting for all its adjacent vertices, then push it to a stack. Finally, print contents of stack. Note that a vertex is pushed to stack only when all of its adjacent vertices (and their adjacent vertices and so on) are already in stack.<\/p>\n

Following are C++ and Java implementations of topological sorting. Please see the code for Depth First Traversal for a disconnected Graph and note the differences between the second code given there and the below code.<\/p>\n[ad type=”banner”]\n

C++ Programming:<\/strong><\/p>\n

<\/div> 
\/\/ A C++ program to print topological sorting of a DAG#include<iostream>#include <list>#include <stack>using namespace std; \/\/ Class to represent a graphclass Graph{    int V;    \/\/ No. of vertices'     \/\/ Pointer to an array containing adjacency listsList    list<int> *adj;     \/\/ A function used by topologicalSort    void topologicalSortUtil(int v, bool visited[], stack<int> &Stack);public:    Graph(int V);   \/\/ Constructor      \/\/ function to add an edge to graph    void addEdge(int v, int w);     \/\/ prints a Topological Sort of the complete graph    void topologicalSort();}; Graph::Graph(int V){    this->V = V;    adj = new list<int>[V];} void Graph::addEdge(int v, int w){    adj[v].push_back(w); \/\/ Add w to v\u2019s list.} \/\/ A recursive function used by topologicalSortvoid Graph::topologicalSortUtil(int v, bool visited[],                                 stack<int> &Stack){    \/\/ Mark the current node as visited.    visited[v] = true;     \/\/ Recur for all the vertices adjacent to this vertex    list<int>::iterator i;    for (i = adj[v].begin(); i != adj[v].end(); ++i)        if (!visited[*i])            topologicalSortUtil(*i, visited, Stack);     \/\/ Push current vertex to stack which stores result    Stack.push(v);} \/\/ The function to do Topological Sort. It uses recursive \/\/ topologicalSortUtil()void Graph::topologicalSort(){    stack<int> Stack;     \/\/ Mark all the vertices as not visited    bool *visited = new bool[V];    for (int i = 0; i < V; i++)        visited[i] = false;     \/\/ Call the recursive helper function to store Topological    \/\/ Sort starting from all vertices one by one    for (int i = 0; i < V; i++)      if (visited[i] == false)        topologicalSortUtil(i, visited, Stack);     \/\/ Print contents of stack    while (Stack.empty() == false)    {        cout << Stack.top() << " ";        Stack.pop();    }} \/\/ Driver program to test above functionsint main(){    \/\/ Create a graph given in the above diagram    Graph g(6);    g.addEdge(5, 2);    g.addEdge(5, 0);    g.addEdge(4, 0);    g.addEdge(4, 1);    g.addEdge(2, 3);    g.addEdge(3, 1);     cout << "Following is a Topological Sort of the given graph \\n";    g.topologicalSort();     return 0;}<\/code><\/pre> <\/div>\n
Output:<\/strong><\/p>\n
Following is a Topological Sort of the given graph\r\n5 4 2 3 1 0<\/pre>\n
Time Complexity: <\/strong>The above algorithm is simply DFS with an extra stack. So time complexity is same as DFS which is O(V+E).<\/p>\n
Applications:<\/strong>
\nTopological Sorting is mainly used for scheduling jobs from the given dependencies among jobs. In computer science, applications of this type arise in instruction scheduling, ordering of formula cell evaluation when recomputing formula values in spreadsheets, logic synthesis, determining the order of compilation tasks to perform in makefiles, data serialization, and resolving symbol dependencies in linkers [2].<\/p>\n[ad type=”banner”]\n
 <\/p>\n","protected":false},"excerpt":{"rendered":"
C++ Algorithm – Topological Sorting – Graph Algorithms – Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[83515,1,74168,73906],"tags":[83607,83605,83609,83608,83604,83606,83610,83611,82146,82385,82145,82149,82457,82144,83589],"class_list":["post-26024","post","type-post","status-publish","format-standard","hentry","category-c-programming-3","category-coding","category-dfs-and-bfs","category-graph-algorithms","tag-algorithm-c-definition","tag-algorithm-c-example","tag-c-algorithm-book","tag-c-algorithm-pdf","tag-c-algorithm-sort","tag-c-algorithm-tutorial","tag-c-stl-algorithm-tutorial","tag-how-to-write-algorithm-for-functions-in-c","tag-topological-sort-algorithm-pseudocode","tag-topological-sort-complexity","tag-topological-sort-example-step-by-step","tag-topological-sort-java","tag-topological-sort-program-in-c","tag-topological-sort-using-dfs","tag-topological-sorting-leetcode"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26024","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26024"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26024\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26024"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26024"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26024"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}