Topological Sort

Topological Sort

Description
Topological sort is an algorithm that linearly orders the vertices of a directed acyclic graph (DAG) such that for every directed edge \(u \to v\), vertex \(u\) comes before vertex \(v\) in the ordering. Topological sort is commonly used for dependency analysis, such as task scheduling and determining compilation order. If the graph contains a cycle, a topological sort is impossible.

Procedure

  1. Understand the Graph Structure

    • Topological sort is performed on a directed graph where each vertex represents a task or event, and edges represent dependencies (e.g., \(u \to v\) means \(v\) can only proceed after \(u\) is completed).
    • Ensure the graph is acyclic; otherwise, dependencies conflict and sorting is impossible.

  2. Calculate Vertex In-Degrees

    • In-degree refers to the number of edges pointing to a vertex. Initially, compute the in-degree of each vertex (e.g., by traversing the edge list).
    • Example: For edge \((u, v)\), the in-degree of vertex \(v\) is increased by 1.

  3. Initialize a Queue

    • Enqueue all vertices with an in-degree of 0 (these vertices have no dependencies and can be processed first).
    • The queue ensures vertices are processed in an order that respects dependencies.

  4. Process Vertices in the Queue

    • Dequeue a vertex \(u\) and append it to the topological sort result list.
    • Traverse all adjacent vertices \(v\) of \(u\) (i.e., edges \(u \to v\)), and decrement the in-degree of \(v\) (indicating that dependency on \(u\) is satisfied).
    • If the in-degree of \(v\) becomes 0, enqueue \(v\) (indicating all prerequisites of \(v\) are completed).

  5. Detect Cycles and Complete Sorting

    • If the final sorted result contains all vertices, the graph is acyclic, and the sort is valid.
    • If the number of vertices in the result is less than the total vertices in the graph, a cycle exists, and topological sort cannot be completed.

Example
Consider a directed graph with edges: \(A \to B\), \(A \to C\), \(B \to D\), \(C \to D\).

  • Step 1: In-degree statistics: A(0), B(1), C(1), D(2).
  • Step 2: Initial queue: [A] (in-degree 0).
  • Step 3: Process A, result list: [A], update in-degrees of B and C (B:0, C:0), queue becomes [B, C].
  • Step 4: Process B, result list: [A, B], update in-degree of D (D:1), queue remains [C].
  • Step 5: Process C, result list: [A, B, C], update in-degree of D (D:0), queue becomes [D].
  • Step 6: Process D, result list: [A, B, C, D].
    The final topological sort is A, B, C, D or A, C, B, D (multiple valid orders depend on queue processing order).

Key Points

  • The time complexity of topological sort is \(O(V + E)\), where \(V\) is the number of vertices and \(E\) is the number of edges.
  • To find all possible orderings, backtracking is required; for a single solution, the queue-based method is more efficient.
  • In practice, optimize queue strategies based on specific scenarios (e.g., parallel task scheduling).