Problem Statement
Given a Directed Acyclic Graph (DAG) with V vertices labeled from 0 to V-1 and E edges.The graph is represented using an adjacency list where adj[i] lists all nodes connected to node. Find any Topological Sorting of that Graph.
In topological sorting, node u will always appear before node v if there is a directed edge from node u towards node v(u -> v).
The Output will be True if your topological sort is correct otherwise it will be False.
Examples
Example 1:
Input: V = 6,adj=[ [ ], [ ], [3], [1], [0,1], [0,2] ]
Output: [5, 4, 2, 3, 1, 0]
Explanation: A graph may have multiple topological sortings.
The result is one of them. The necessary conditions
for the ordering are:
According to edge 5 -> 0, node 5 must appear before node 0 in the ordering.
According to edge 4 -> 0, node 4 must appear before node 0 in the ordering.
According to edge 5 -> 2, node 5 must appear before node 2 in the ordering.
According to edge 2 -> 3, node 2 must appear before node 3 in the ordering.
According to edge 3 -> 1, node 3 must appear before node 1 in the ordering.
According to edge 4 -> 1, node 4 must appear before node 1 in the ordering.
The above result satisfies all the necessary conditions.
[4, 5, 2, 3, 1, 0] is also one such topological sorting
that satisfies all the conditions.Different Approaches
1️⃣ DFS
Intuition:
The topological sorting of a directed acyclic graph is nothing but the linear ordering of vertices such that if there is an edge between node u and v(u -> v), node u appears before v in that ordering.
Why does topological sort only exist in DAG?
- If the edges are undirected: An undirected edge between node u and v signifies an edge from u to v (u->v) as well as from v to u (v->u) making it practically impossible to write such orderings where u appears before v and v appears before u simultaneously.
- If the directed graph contains a cycle: There is no linear ordering possible for nodes in cycles, making it impossible for topological sorting to exist.
Understanding:
Depth-first search (DFS) is a natural fit for this problem because it allows us to explore each path of the graph deeply before backtracking, ensuring that all dependencies of a node are processed before the node itself.
- During the DFS traversal, when a node is fully processed (i.e., all nodes it points to are visited), we push it onto a stack.
- This stack helps us reverse the order of processing, as nodes deeper in the graph (dependent nodes) are pushed onto the stack first. When we later pop from the stack, we get the nodes in the correct topological order.
Approach:
- Prepare a list to store the topological order. Initialize a stack to keep track of the nodes in reverse order of their processing. Create a visited array to track which nodes have been visited.
- Define a recursive DFS function that marks the current node as visited. For each neighbor of the current node, if it is not visited, recursively perform DFS on it. After all neighbors are processed, push the current node onto the stack.
- Traverse all nodes in the graph. For each unvisited node, initiate a DFS traversal.
- Once DFS is complete for all nodes, pop elements from the stack one by one and add them to the topological order list.
Code:
#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Function to perform DFS traversal
void dfs(int node, vector<int> adj[],
vector<int> &vis,
stack <int> &st) {
// Mark the node as visited
vis[node] = 1;
// Traverse all the neighbors
for(auto it : adj[node]) {
// If not visited, recursively perform DFS.
if(vis[it] == 0) dfs(it, adj, vis, st);
}
/* Add the current node to stack
once all the nodes connected to it
have been processed */
st.push(node);
}
public:
/* Function to return list containing
vertices in Topological order */
vector<int> topoSort(int V, vector<int> adj[])
{
// To store the result
vector <int> ans;
/* Stack to store processed
nodes in reverse order */
stack <int> st;
// Visited array
vector<int> vis(V, 0);
// Traverse the graph
for(int i=0; i<V; i++) {
// Start DFS traversal for unvisited node
if(!vis[i]) {
dfs(i, adj, vis, st);
}
}
// Until the stack is empty
while(!st.empty()) {
// Add the top of stack to result
ans.push_back(st.top());
// Pop the top node
st.pop();
}
// Return the result
return ans;
}
};
int main() {
int V = 6;
vector<int> adj[V] = {
{},
{},
{3},
{1},
{0,1},
{0,2}
};
/* Creating an instance of
Solution class */
Solution sol;
/* Function call to return the
topological sorting of given graph */
vector<int> ans = sol.topoSort(V, adj);
// Output
cout << "The topological sorting of the given graph is: \n";
for(int i=0; i < V; i++) {
cout << ans[i] << " ";
}
return 0;
}Complexity Analysis:
- Time Complexity: O(V+E) (where V and E represent the number of nodes and edges in the graph)
A simple DFS traversal takes O(V+E) time. - Space Complexity: O(V)
The stack will store at most V nodes taking O(V) space and the array to store the topological sort takes O(V) space.
2️⃣ BFS (Kahn's Algorithm)
Intuition:
The topological sorting of a directed acyclic graph is nothing but the linear ordering of vertices such that if there is an edge between node u and v(u -> v), node u appears before v in that ordering.
Why does topological sort only exist in DAG?
- If the edges are undirected: An undirected edge between node u and v signifies an edge from u to v (u->v) as well as from v to u (v->u) making it practically impossible to write such orderings where u appears before v and v appears before u simultaneously.
- If the directed graph contains a cycle: There is no linear ordering possible for nodes in cycles, making it impossible for topological sorting to exist.
To solve the problem using BFS traversal, Kahn's algorithm can be used.
Kahn's Algorithm:
The algorithm suggests that there will always be at least one node having in-degree as zero, which means all such nodes can be put before any other node in the ordering as there is no node pointing to any of these nodes.
After such nodes are added to the ordering, the edges from these nodes can be removed, updating the in-degree of other nodes and exposing more nodes having an in-degree of zero. This process can be repeated till there are nodes left in the graph to get the required linear ordering.
Approach:
- Prepare a list to store the topological order. Create an array to track the in-degree (number of incoming edges) of each node. Traverse each node and update the in-degree of its neighbors based on the adjacency list representation of the graph.
- Initialize a queue and add all nodes with zero in-degree to it. These nodes have no dependencies and can be processed first.
- Use a loop to process nodes from the queue until it is empty:
- Remove a node from the front of the queue and add it to the topological order list.
- For each neighbor of the removed node, reduce its in-degree by one.
- If a neighbor's in-degree becomes zero, all its parent nodes are processed so add it to the queue.
- After processing all nodes, the topological order list will contain a valid topological sorting of the graph.
Code:
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/* Function to return the topological
sorting of given graph */
vector<int> topoSort(int V, vector<int> adj[]) {
// To store the result
vector<int> ans;
// To store the In-degrees of nodes
vector<int> inDegree(V, 0);
// Calculating the In-degree of the given graph
for(int i=0; i<V; i++) {
for(auto it : adj[i]) inDegree[it]++;
}
// Queue to facilitate BFS
queue<int> q;
// Add the nodes with no in-degree to queue
for(int i=0; i<V; i++) {
if(inDegree[i] == 0) q.push(i);
}
// Until the queue is empty
while(!q.empty()) {
// Get the node
int node = q.front();
// Add it to the answer
ans.push_back(node);
q.pop();
// Traverse the neighbours
for(auto it : adj[node]) {
// Decrement the in-degree
inDegree[it]--;
/* Add the node to queue if
its in-degree becomes zero */
if(inDegree[it] == 0) q.push(it);
}
}
// Return the result
return ans;
}
};
int main() {
int V = 6;
vector<int> adj[V] = {
{},
{},
{3},
{1},
{0,1},
{0,2}
};
/* Creating an instance of
Solution class */
Solution sol;
/* Function call to return the
topological sorting of given graph */
vector<int> ans = sol.topoSort(V, adj);
// Output
cout << "The topological sorting of the given graph is: \n";
for(int i=0; i < V; i++) {
cout << ans[i] << " ";
}
return 0;
}Complexity Analysis:
- Time Complexity: O(V+E) (where V and E represent the number of nodes and edges in the graph)
A simple BFS traversal takes O(V+E) time. - Space Complexity: O(V)
Array to store in-degrees require O(V) space and queue space will store O(V) nodes at maximum.