A translation of the article was prepared ahead of the start of the course "Algorithms for Developers" .
Topological sorting for a directed acyclic graph (Directed Acyclic Graphs, hereinafter referred to as DAG) is a linear ordering of vertices for which the following condition holds: for each directed edge uv, the vertex u precedes the vertex v in the ordering. If the graph is not a DAG, then topological sorting is not possible for it.For example, the topological sorting of the graph below is “5 4 2 3 1 0”. There can be several topological sortings for a graph. For example, another topological sorting for the same graph is “4 5 2 3 1 0”. The first vertex in topological sorting is always the vertex without incoming edges.
Topological sorting vs deep walk:When going deep(Depth First Traversal, hereinafter referred to as DFS ) we output the vertex and then recursively call DFS for adjacent vertices. In topological sorting, we need to display the vertex in front of its adjacent vertices. For example, in this graph, the vertex “5” should be displayed before the vertex “0”, and, unlike DFS , the vertex “4” should also be displayed before the vertex “0”. This distinguishes topological sorting from DFS. For example, the DFS of the column above is “5 2 3 1 0 4”, but this is not a topological sort.Recommendation: before moving on to the implementation of the algorithm, first try to understand the task in practice .Topological sorting search algorithm.To get started, we recommend that you familiarize yourself with this DFS implementation. We can modify DFS so that a topological sorting of the graph is obtained. In dfswe start with a suitable vertex, which we first output, and then recursively call DFS for its adjacent vertices. In topological sorting, we use a temporary stack. A vertex is not displayed immediately - first, topological sorting is called for all adjacent vertices, then the vertex is pushed onto the stack. Only after traversing all the vertices is the contents of the stack displayed. Note that a vertex is pushed onto the stack only when all adjacent vertices (and their adjacent vertices, etc.) are already on the stack.The image below is an illustration of the above approach:
:
(G)
0 →
1→
2 → 3
3 → 1
4 → 0, 1
5 → 2, 0
1:
(0), visited[0] = true
. .
0
2:
(1), visited[1] = true
. .
0 1
3:
(2),, visited[2] = true
(3),, visited[3] = true
1 .
0 1 3 2
4:
(4),, visited[4] = true
Vertices 0 and 1 are already visited. No more recursive calls.
Stack 0 1 3 2 4
Step 5:
Topological sorting (5), visited [5] = true
Vertices 2 and 0 are already visited. No more recursive calls.
Stack 0 1 3 2 4 5
Step 6:
Pull all stack items from top to bottom
The following are topological sort implementations. Please check out the DFT implementation for a disconnected graph and note the differences between the second code given there and the code below.C ++
#include<iostream>
#include <list>
#include <stack>
using namespace std;
class Graph
{
int V;
list<int> *adj;
void topologicalSortUtil(int v, bool visited[], stack<int> &Stack);
public:
Graph(int V);
void addEdge(int v, int w);
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);
}
void Graph::topologicalSortUtil(int v, bool visited[],
stack<int> &Stack)
{
visited[v] = true;
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
topologicalSortUtil(*i, visited, Stack);
Stack.push(v);
}
void Graph::topologicalSort()
{
stack<int> Stack;
bool *visited = new bool[V];
for (int i = 0; i < V; i++)
visited[i] = false;
for (int i = 0; i < V; i++)
if (visited[i] == false)
topologicalSortUtil(i, visited, Stack);
while (Stack.empty() == false)
{
cout << Stack.top() << " ";
Stack.pop();
}
}
int main()
{
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;
}
Java
import java.io.*;
import java.util.*;
class Graph
{
private int V;
private LinkedList<Integer> adj[];
Graph(int v)
{
V = v;
adj = new LinkedList[v];
for (int i=0; i<v; ++i)
adj[i] = new LinkedList();
}
void addEdge(int v,int w) { adj[v].add(w); }
void topologicalSortUtil(int v, boolean visited[],
Stack stack)
{
visited[v] = true;
Integer i;
Iterator<Integer> it = adj[v].iterator();
while (it.hasNext())
{
i = it.next();
if (!visited[i])
topologicalSortUtil(i, visited, stack);
}
stack.push(new Integer(v));
}
void topologicalSort()
{
Stack stack = new Stack();
boolean visited[] = new boolean[V];
for (int i = 0; i < V; i++)
visited[i] = false;
for (int i = 0; i < V; i++)
if (visited[i] == false)
topologicalSortUtil(i, visited, stack);
while (stack.empty()==false)
System.out.print(stack.pop() + " ");
}
public static void main(String args[])
{
Graph g = new Graph(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);
System.out.println("Following is a Topological " +
"sort of the given graph");
g.topologicalSort();
}
}
Python
class Graph:
def __init__(self,vertices):
self.graph = defaultdict(list)
self.V = vertices
def addEdge(self,u,v):
self.graph[u].append(v)
def topologicalSortUtil(self,v,visited,stack):
visited[v] = True
for i in self.graph[v]:
if visited[i] == False:
self.topologicalSortUtil(i,visited,stack)
stack.insert(0,v)
def topologicalSort(self):
visited = [False]*self.V
stack =[]
for i in range(self.V):
if visited[i] == False:
self.topologicalSortUtil(i,visited,stack)
print stack
g= Graph(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);
print "Following is a Topological Sort of the given graph"
g.topologicalSort()
<b>:</b>
Following is a Topological Sort of the given graph
5 4 2 3 1 0
Difficulty in time: the above algorithm is DFS with an additional stack. Thus, the time complexity is the same as that of DFS, which is O (V + E).Note: you can also use a vector instead of a stack. If you use a vector to get topological sorting, you need to output the elements in the reverse order.Application:Topological sorting is mainly used for scheduling work from given dependencies between them. In computer science, it is used to plan commands, organize cells for calculating formulas when recalculating formula values in spreadsheets, logical synthesis, determining the order of compilation tasks to be performed in makefiles, data serialization, and resolving symbolic dependencies in linkers [ 2 ].Related Articles
Kahn algorithm for topological sorting : another O (V + E) algorithm.All topological sortings of an oriented acyclic graphReferences
http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/topoSort.htmhttp://en.wikipedia.org/wiki/Topological_sortingPlease leave a comment if you find an error, or if you want to share additional information on the topic under discussion.
Learn more about the course.