Topological Sort

Introduction

Topological Sorting for a Directed Acyclic Graph (DAG) is a linear ordering of its vertices such that for every directed edge 𝑢→𝑣 , vertex 𝑢 appears before 𝑣 in the ordering. It is only applicable to DAGs, as cycles prevent a valid order. The sorting begins with vertices that have no incoming edges (in-degree 0).

How Topological Sort Works?

Understand the Graph Structure

• Topological Sort is applicable only to Directed Acyclic Graphs (DAGs). A DAG is a graph with directed edges and no cycles.

• In a topological sort, you arrange the vertices in a linear order such that for every directed edge u → v, u comes before v in the ordering.

Initialize the Data Structures

You need two main things:

• Visited Array: This keeps track of which nodes have been visited.
• Stack: The stack stores nodes in the topological order.

Perform DFS (Depth-First Search)

• Start a DFS from each unvisited node. The idea is to explore all the descendants of a node before returning to it.

For each node, do the following:

• Mark the node as visited.
• Explore all its unvisited neighbors (connected nodes).
• Recursively apply DFS on each neighbor.

Add Node to Stack after DFS

• After all the neighbors of a node have been visited, push the node onto the stack. This ensures that a node appears before its descendants in the topological order.

Repeat for All Nodes

• Repeat the DFS for every unvisited node in the graph, ensuring that you cover all disconnected parts of the graph.

Retrieve the Topological Order

• After performing DFS on all nodes, the stack will contain the nodes in the reverse topological order.
• Pop all elements from the stack and the resulting order will be the topological sort of the graph.

Previous slideNext slide

Implementation of Topological Sort

//topologicalsort.cpp
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
void dfs(vector<bool> &visited, vector<vector<int>> &adj, int u, stack<int> &st)
{
visited[u] = true;
for (int &v : adj[u])
{
    if (!visited[v])
    {
        dfs(visited, adj, v, st);
    }
}
st.push(u);
}

vector<int> topologicalSort(vector<vector<int>> &adj)
{
stack<int> st;
vector<bool> visited(adj.size(), 0);
vector<int> ans(adj.size());
for (int i = 0; i < adj.size(); i++)
{
    if (!visited[i])
    {
        dfs(visited, adj, i, st);
    }
}
int i = 0;
while (!st.empty())
{
    ans[i++] = st.top();
    st.pop();
}
return ans;
}
int main()
{
int n = 6; 
vector<vector<int>> adj = {
    {2, 3},   // 0 → 2, 0 → 3
    {4},       // 1 → 4
    {1,3},       // 2 → 1,2->3
    {1},       // 3 → 1
    {},       //
    {1,4}         // 5->1,5->4
};

vector<int> result = topologicalSort(adj);

for (int node : result) {
    cout << node << " ";
}

return 0;
} 

Time Complexity

DFS Traversal:

• The dfs function visits each node and explores all its outgoing edges.

• For a graph with V vertices and E edges, the DFS traversal will visit each vertex once and explore each edge once.

• The time complexity of DFS is O(V + E).

Topological Sort:

• The topologicalSort function iterates over all the vertices and performs DFS on any unvisited vertex. Each DFS visit will add vertices to a stack and eventually form the topological order.

• So, the overall time complexity for the entire topological sort process is O(V + E).

Time Complexity: O(V + E)

Space Complexity

Visited Array:

• We maintain a visited array of size V, which takes O(V) space.

Adjacency List:

• The adjacency list adj is of size V, and each list inside it holds edges for the corresponding vertex. The total space taken by the adjacency list is O(V + E).

Stack:

• The stack stores the vertices as we process them in DFS. In the worst case, the stack will hold all V vertices at once. So, it requires O(V) space.

Result Array:

• The ans array stores the topological order, which also takes O(V) space.

Space Complexity: O(V + E)