Grokking the Coding Interview: Patterns for Coding Questions
Ask Author
Back to course home

0% completed

Vote For New Content
Introduction to Topological Sort
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

What is Topological Sorting?

Topological sorting is a method used to order the vertices of a directed graph such that for every directed edge u \rightarrow v, vertex (u) comes before (v) in the ordering. This concept is crucial in scenarios where there is a dependency between tasks or elements.

For instance, in task scheduling, some tasks must be completed before others, making topological sorting a useful technique.

Topological Sorting in Directed Acyclic Graphs (DAGs)

Topological sorting is applicable exclusively to Directed Acyclic Graphs (DAGs). A DAG is a directed graph that contains no cycles. The absence of cycles ensures that there is a clear direction or hierarchy within the graph, which is essential for topological sorting.

In a DAG, it is always possible to achieve a topological order of the vertices. This order respects the direction of the edges, meaning that if there is a directed edge from vertex (u) to vertex (v), (u) will appear before (v) in the topological order.

Topological Order May Not Be Unique

One of the interesting aspects of topological sorting is that the order may not be unique. Depending on the structure of the graph, there could be multiple valid topological orders. This is particularly true when the graph contains vertices with no incoming edges (indegree 0) at multiple stages.

For example, consider a scenario where two vertices, (u) and (v), both have no incoming edges and are not connected to each other. In this case, either (u) or (v) can appear first in the topological order, resulting in multiple valid topological sequences.

Example with Multiple Topological Sorting Outcomes:

Consider the following Directed Acyclic Graph (DAG):

    5        7
   / \      / \
  2   0    3   4
   \ /    /     \
    6    1       8

In this graph, there are several possible topological sorts:

  1. Order 1: 7, 5, 2, 6, 3, 1, 0, 4, 8
  2. Order 2: 7, 5, 2, 3, 1, 0, 4, 6, 8
  3. Order 3: 5, 7, 3, 2, 1, 6, 0, 4, 8

In each of these orders, the vertices respect the direction of the edges. For example, in Order 1, vertex 7 appears before vertices 3 and 4, which it points to. Similarly, vertex 5 appears before vertices 2 and 0, which it points to. This demonstrates that while the topological sort maintains the required dependencies, the exact order can vary depending on the choice of starting points and the order in which vertices are processed.

Topological Sort Using DFS

Topological sorting using Depth First Search (DFS) involves visiting all vertices in a depth-first manner. When visiting a vertex, we recursively visit all its adjacent vertices that have not been visited. After visiting all adjacent vertices, we add the current vertex to a stack. This ensures that the current vertex is processed only after all vertices it depends on are processed. Finally, we pop vertices from the stack to get the topological order.

Step-by-Step Algorithm

  1. Initialization:

    • Create a stack to store the topological sort result.
    • Mark all vertices as not visited.

  2. Recursive DFS Utility Function (topologicalSortUtil):

    • Mark the current vertex as visited.
    • For each adjacent vertex, if it is not visited, recursively call topologicalSortUtil for that vertex.
    • After visiting all adjacent vertices, push the current vertex onto the stack.

  3. Topological Sort Function (topologicalSort):

    • For each vertex, if it is not visited, call the recursive DFS utility function.
    • Once all vertices are processed, pop elements from the stack to get the topological order.

Algorithm Walkthrough

Consider the following directed acyclic graph (DAG):

    5 → 2
    5 → 0
    4 → 0
    4 → 1
    2 → 3
    3 → 1
Image

Let's walk through the algorithm step-by-step using the provided code:

  1. Initialization:

    • Create a stack stack = [].
    • Mark all vertices as not visited visited = [False, False, False, False, False, False].

  2. Processing Vertex 0:

    • Vertex 0 is not visited.
    • Call topologicalSortUtil(0, visited, stack).
    • Mark vertex 0 as visited visited[0] = True.
    • Vertex 0 has no outgoing edges.
    • Push vertex 0 onto the stack stack = [0].

  3. Processing Vertex 1:

    • Vertex 1 is not visited.
    • Call topologicalSortUtil(1, visited, stack).
    • Mark vertex 1 as visited visited[1] = True.
    • Vertex 1 has no outgoing edges.
    • Push vertex 1 onto the stack stack = [1, 0].

  4. Processing Vertex 2:

    • Vertex 2 is not visited.
    • Call topologicalSortUtil(2, visited, stack).
    • Mark vertex 2 as visited visited[2] = True.
    • Vertex 2 has an outgoing edge to vertex 3.
    • Start processing vertex 3.

  5. Processing Vertex 3:

    • Vertex 3 is not visited.
    • Call topologicalSortUtil(3, visited, stack).
    • Mark vertex 3 as visited visited[3] = True.
    • Vertex 3 has an outgoing edge to vertex 1, but vertex 1 is already visited.
    • Push vertex 3 onto the stack stack = [3, 1, 0].
    • Return to processing vertex 2.

  6. Returning to Vertex 2:

    • Vertex 2 has no unvisited adjacent vertices left.
    • Push vertex 2 onto the stack stack = [2, 3, 1, 0].

  7. Processing Vertex 4:

    • Vertex 4 is not visited.
    • Call topologicalSortUtil(4, visited, stack).
    • Mark vertex 4 as visited visited[4] = True.
    • Vertex 4 has outgoing edges to vertices 0 and 1, both of which are already visited.
    • Push vertex 4 onto the stack stack = [4, 2, 3, 1, 0].

  8. Processing Vertex 5:

    • Vertex 5 is not visited.
    • Call topologicalSortUtil(5, visited, stack).
    • Mark vertex 5 as visited visited[5] = True.
    • Vertex 5 has outgoing edges to vertices 2 and 0, both of which are already visited.
    • Push vertex 5 onto the stack stack = [5, 4, 2, 3, 1, 0].

Code

Python3
Python3
. . . .

Complexity Analysis:

  • Time Complexity: The time complexity of the DFS-based topological sorting algorithm is O(V + E), where (V) is the number of vertices and (E) is the number of edges in the graph. This is because each vertex and edge is processed exactly once.
  • Space Complexity: The space complexity is O(V) due to the stack and the visited array used to keep track of the visited vertices. The adjacency list representation of the graph also requires O(V + E) space.

Topological Sort Using BFS (Kahn's Algorithm)

Kahn's Algorithm for topological sorting uses BFS to process nodes in a way that respects the dependencies. The algorithm works by repeatedly removing nodes with no incoming edges and recording them. This ensures that each node is only processed after all its dependencies have been processed.

Step-by-Step Algorithm

  1. Initialization:

    • Create an in-degree array to keep track of the number of incoming edges for each vertex.
    • Initialize the in-degree of all vertices to 0.
    • Create a queue to store all vertices with in-degree 0.

  2. Calculate In-degree:

    • For each vertex, iterate through its adjacency list and increase the in-degree of its neighbors by 1.

  3. Enqueue Vertices with In-degree 0:

    • Iterate through the in-degree array and enqueue all vertices with in-degree 0 into the queue.

  4. Process Vertices:

    • While the queue is not empty:
      • Dequeue a vertex from the queue.
      • Add the dequeued vertex to the topological order list.
      • For each neighbor of the dequeued vertex:
        • Decrease the in-degree of the neighbor by 1.
        • If the in-degree of the neighbor becomes 0, enqueue the neighbor.

  5. Check for Cycles:

    • If the number of vertices in the topological order list is less than the total number of vertices, there is a cycle in the graph, and topological sorting is not possible.

  6. Output the Topological Order:

    • Print or return the topological order list.

Algorithm Walkthrough

Consider the following directed acyclic graph (DAG):

    5 → 2
    5 → 0
    4 → 0
    4 → 1
    2 → 3
    3 → 1

  1. Initialization:

    • inDegree = [0, 0, 0, 0, 0, 0]
    • queue = []
    • topOrder = []

  2. Calculate In-degree:

    • For vertex 5: inDegree = [1, 0, 1, 0, 0, 0]
    • For vertex 4: inDegree = [2, 1, 1, 0, 0, 0]
    • For vertex 2: inDegree = [2, 1, 1, 1, 0, 0]
    • For vertex 3: inDegree = [2, 2, 1, 1, 0, 0]

  3. Enqueue Vertices with In-degree 0:

    • Vertices with in-degree 0: 4, 5
    • queue = [4, 5]

  4. Process Vertices:

    • Dequeue 4:
      • topOrder = [4]
      • Decrease in-degree of neighbors 0 and 1:
        • inDegree = [1, 1, 1, 1, 0, 0]
      • No new vertices with in-degree 0.
      • queue = [5]
    • Dequeue 5:
      • topOrder = [4, 5]
      • Decrease in-degree of neighbors 2 and 0:
        • inDegree = [0, 1, 0, 1, 0, 0]
      • Add 2 and 0 to the queue (both now have in-degree 0).
      • queue = [2, 0]
    • Dequeue 2:
      • topOrder = [4, 5, 2]
      • Decrease in-degree of neighbor 3:
        • inDegree = [0, 1, 0, 0, 0, 0]
      • Add 3 to the queue (now has in-degree 0).
      • queue = [0, 3]
    • Dequeue 0:
      • topOrder = [4, 5, 2, 0]
      • queue = [3]
    • Dequeue 3:
      • topOrder = [4, 5, 2, 0, 3]
      • Decrease in-degree of neighbor 1:
        • inDegree = [0, 0, 0, 0, 0, 0]
      • Add 1 to the queue (now has in-degree 0).
      • queue = [1]
    • Dequeue 1:
      • topOrder = [4, 5, 2, 0, 3, 1]
      • queue = []

  5. Check for Cycles:

    • The number of vertices in topOrder is equal to the number of vertices in the graph, so there are no cycles.

  6. Output the Topological Order:

    • The topological order is: 4, 5, 2, 0, 3, 1.

Code

Python3
Python3
. . . .

Complexity Analysis

Time Complexity

  • Initialization of in-degree array: O(V + E)
    • Calculating the in-degree for all vertices involves iterating over all the vertices and their edges.
  • Processing vertices: O(V + E)
    • Enqueuing and dequeuing vertices takes O(V) time.
    • For each vertex, we reduce the in-degree of its neighbors, which takes O(E) time in total.

Overall, the time complexity is O(V + E), where (V) is the number of vertices and (E) is the number of edges.

Space Complexity

  • Adjacency list: O(V + E)
  • In-degree array: O(V)
  • Queue: O(V)
  • Topological order list: O(V)

Overall, the space complexity is O(V + E).

Pros, Cons, and Applications of Topological Sorting

Pros

  1. Linear Ordering

    • Provides a linear order of vertices that respects the dependencies among them.

  2. Simple and Efficient

    • Both DFS and Kahn's Algorithm for topological sorting are simple to understand and implement.
    • The time complexity of O(V + E) is efficient for most practical purposes.

  3. Detecting Cycles

    • Useful for detecting cycles in a directed graph. If the topological sort is not possible, it indicates the presence of a cycle.

Cons

  1. Applicable Only to DAGs

    • Topological sorting can only be applied to Directed Acyclic Graphs (DAGs). It cannot be used for graphs with cycles or undirected graphs.

  2. No Unique Order

    • There may be multiple valid topological sorts for a given graph, depending on the graph's structure and the order in which vertices are processed.

  3. Extra Space

    • Requires additional space for storing the in-degree array (in Kahn's Algorithm) and the stack or queue used during the sorting process.

Applications

  1. Task Scheduling

    • Used to schedule tasks where certain tasks must be completed before others. For example, in project management, where tasks have dependencies.

  2. Course Prerequisites

    • Determining the order in which courses should be taken when some courses are prerequisites for others.

  3. Build Systems

    • Used in build systems to determine the order in which components or modules should be compiled, where some modules depend on others.

  4. Dependency Resolution

    • Used in package managers and dependency resolution systems to install software packages in the correct order, respecting dependencies.

  5. Instruction Scheduling

    • In computer architecture, used to schedule instructions in a pipeline while respecting data dependencies.

  6. Compiler Design

    • Used in compiler design for various purposes such as ordering of compilation tasks, resolving symbol dependencies, and so on.

Now, let's start solving the problems related to topological sort.

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible