Problem Statment:
Topological Sort of a directed graph (a graph with unidirectional edges) is a linear ordering of its vertices such that for every directed edge (U, V) from vertex U to vertex V, U comes before V in the ordering.
Given a directed graph, find the topological ordering of its vertices.
Example 1:
Input: vertices=4, edges=[[3, 2], [3, 0], [2, 0], [2, 1]] Output: Following are the two valid topological sorts for the given graph: 1) 3, 2, 0, 1 2) 3, 2, 1, 0
Example 2:
Input: vertices=6, edges=[[0, 1], [0, 3], [1, 2], [1, 3], [2, 3], [2, 4], [2, 5], [3, 4], [3, 5], [4, 5]] Output: 0, 1, 2, 3, 4, 5
Example 3:
Input: vertices=7, edges=[[6, 4], [6, 2], [5, 3], [5, 4], [3, 0], [3, 1], [3, 2], [4, 1]] Output: Following are all valid topological sorts for the given graph: 1) 5, 6, 3, 4, 0, 1, 2 2) 6, 5, 3, 4, 0, 1, 2 3) 5, 6, 4, 3, 0, 2, 1 4) 6, 5, 4, 3, 0, 1, 2 5) 5, 6, 3, 4, 0, 2, 1 6) 5, 6, 3, 4, 1, 2, 0 There are other valid topological ordering of the graph too.
Solution:
As a rule, cyclic graphs don’t have valid topological orderings. Let’s look at the below graph.
In this graph, 0 comes before 1, 1 comes before 2, and 2 comes before 0. So, here we cannot decide what comes first. So, if there is any cycle in the graph, Topological Ordering is not possible. Hence, the Graph has to be Directed Acyclic Graph.
Approach:
- Source: Any node that has no incoming edge and has only outgoing edges is called a source.
- Sink: Any node that has only incoming edges and no outgoing edge is called a sink.
So, we can say that a topological ordering starts with one of the sources and ends at one of the sinks. If there are two sources, then we can start with anyone until specified some special criteria.
Now, think carefully, if there is any node whose in-degree is 0, that means, this node can act as a source node. So, we will try to maintain a HashMap in which we will store the count of in-degree for each of the nodes.
Also, we will create an Adjacency List to store the graph.
Let’s look at the algorithm stepwise.
Initial Setup:
- Create an Adjacency List to store the graph.
- Create a HashMap to store the in-degree count for each node. Any node with an in-degree count of 0, will be our source node.
Pre Processing:
Iterate over the HashMap of in-degree. And store all the source nodes i.e nodes with an in-degree count of 0 into a Queue.
Post Processing:
1. For each source, do the following:
- Add it to the sorted list (answer).
- Get all of its children from the graph.
- Decrement the in-degree of each child by 1.
- If a child’s in-degree becomes ‘0’, add it to the source Queue.
2. Repeat step 1, until the Queue becomes empty.
Let’s look at the pictorial representation.
Note: We recommend you to go through the pictorial representation and then come back again to the above steps and understand it.
Now, we will pick all those nodes from inDegreeMap whose count is 0 and add them to the Queue.
After this, we will remove the one-one element from the Queue and add it to the answer. Also, we will decrement the in-degree count of the neighbors of the removed node. Let’s look at it in action.
In the above step, we added 5 and 6 as source nodes into the Queue. When we removed node 5 from the Queue, we also decremented the in-degree count of its neighbors and if the in-degree of any neighbor becomes 0 then the neighbor becomes the source node and is added to the Queue. Similarly, for 6 is done. And hence nodes 3 and 4 are added to the Queue as source nodes.
Finally, the queue will become empty and hence we will have our answer.
One thing to note here is, that the queue will become empty in the case of the Cyclic graph also. But that doesn’t really mean that we will have our required answer. So, when the queue becomes empty, we will check that the answer that we have got, its length should be equal to the number of vertices present in the Graph.
You can try with one example in a similar fashion containing a cycle.
Let’s jump on to the code.
Code:
import java.util.*;
class TopologicalSort {
public static List<Integer> topologicalSort(int edges[][], int vertices) {
List<Integer> sortedOrder = new ArrayList<>();
if(vertices < 0) {
return sortedOrder;
}
HashMap<Integer, Integer> inDegree = new HashMap<>();
HashMap<Integer, ArrayList<Integer>> graph = new HashMap<>();
// intializing the graph
for(int i = 0; i < vertices; i++) {
inDegree.put(i, 0);
graph.put(i, new ArrayList<>());
}
// building the graph
for(int i = 0; i < edges.length; i++) {
int parent = edges[i][0];
int child = edges[i][1];
graph.get(parent).add(child);
inDegree.put(child, inDegree.get(child) + 1);
}
// processing all valid starting nodes
Queue<Integer> queue = new LinkedList<>();
for(Map.Entry<Integer, Integer> entry : inDegree.entrySet()) {
if(entry.getValue() == 0) {
queue.offer(entry.getKey());
}
}
while(!queue.isEmpty()) {
int vertex = queue.poll();
sortedOrder.add(vertex);
List<Integer> children = graph.get(vertex);
for(int child : children) {
inDegree.put(child, inDegree.get(child) - 1);
if(inDegree.get(child) == 0) {
queue.offer(child);
}
}
}
if(sortedOrder.size() != vertices) {
return new ArrayList<>();
}
return sortedOrder;
}
public static void main(String[] args) {
int edges[][] = new int[][] {{6, 2}, {6, 4}, {5, 3}, {5, 4}, {4, 1}, {3, 0}, {3, 1}, {3, 2}};
List<Integer> ans = topologicalSort(edges, 7);
for(int a : ans) {
System.out.print(a + " ");
}
}
}
#include <bits/stdc++.h>
using namespace std;
vector<int> topologicalSort(vector<vector<int>> edges, int vertices) {
vector<int> sortedOrder;
if(vertices <= 0) {
return sortedOrder;
}
map<int, int> inDegree;
map<int, vector<int>> graph;
// intializing the graph
for(int i = 0; i < vertices; i++) {
inDegree[i] = 0;
vector<int> v;
graph[i] = v;
}
// building the graph
for(int i = 0; i < edges.size(); i++) {
int parent = edges[i][0];
int child = edges[i][1];
graph[parent].push_back(child);
inDegree[child] += 1;
}
// processing all valid starting nodes
queue<int> q;
for(auto entry : inDegree) {
if(entry.second == 0) {
q.push(entry.first);
}
}
while(!q.empty()) {
int vertex = q.front();
q.pop();
sortedOrder.push_back(vertex);
vector<int> children = graph[vertex];
for(auto child : children) {
inDegree[child] -= 1;
if(inDegree[child] == 0) {
q.push(child);
}
}
}
if(sortedOrder.size() != vertices) {
vector<int> v;
return v;
}
return sortedOrder;
}
int main(int argc, char const *argv[]) {
vector<vector<int>> edges {{6, 2}, {6, 4}, {5, 3}, {5, 4}, {4, 1}, {3, 0}, {3, 1}, {3, 2}};
vector<int> ans = topologicalSort(edges, 7);
for(auto a : ans) {
cout << a << " ";
}
return 0;
}
from collections import deque def topologicalSort(edges, vertices): sorted_order = [] if(vertices <= 0): return sorted_order in_degree = dict() graph = dict() # intializing the graph for i in range(vertices): in_degree[i] = 0 graph[i] = [] # building the graph for i in range(len(edges)): parent = edges[i][0] child = edges[i][1] in_degree[child] += 1 graph[parent].append(child) # processing all valid starting nodes queue = deque() for key in in_degree: if in_degree[key] == 0: queue.append(key) while queue: vertex = queue.popleft() sorted_order.append(vertex) children = graph[vertex] for child in children: in_degree[child] -= 1 if in_degree[child] == 0: queue.append(child) if len(sorted_order) != vertices: return [] return sorted_order if __name__ == '__main__': edges = [[6, 2], [6, 4], [5, 3], [5, 4], [4, 1], [3, 0], [3, 1], [3, 2]] ans = topologicalSort(edges, 7) for a in ans: print(a, end = " ")
Output:
5 6 3 4 0 2 1
Time and Space Complexity:
Breaking the algorithm into chunks, we:
- Determine the indegree for each node. This is O(E) time (where E is the number of edges), since this involves looking at each directed edge in the graph once.
- Find nodes with no incoming edges. This is a simple loop through all the nodes with some number of constant-time appends. O(V) time (where V is the number of nodes/vertices).
- Add nodes until we run out of nodes with no incoming edges. This loop could run once for every node—O(V) times. In the body, we:
- Do two constant-time operations on an array to add a node to the topological ordering.
- Decrement the indegree for each neighbor of the node we added. Over the entire algorithm, we’ll end up doing exactly one decrement for each edge, making this step O(E) time overall.
- Check if we included all nodes or found a cycle. This is a fast O(1) comparison.
Altogether, the Time Complexity: O(V+E).
That’s the fastest time we can expect since we’ll have to look at all the nodes and edges at least once.
What about Space Complexity? Here are the data structures we created:
- indegree — this has one entry for each node in the graph, so it’s O(V) space.
- queue — this would start out containing every node, so it’s O(V) space in the worst case.
- sortedOrder — in a graph with no cycles, this will eventually have every node. O(V) space.
- graph — the adjacency list, this will eventually store all the edges. O(V + E) space.
Hence, Overall Space Complexity: O(V + E).