Coursify

Design and Analysis of Algorithms (DAA)

Topological Sorting & Network Flow

40 mins

Understand how to order dependencies using Topological Sorting, and learn how to calculate the maximum possible data/liquid throughput in a network using the Ford-Fulkerson method.

Learning Goals

  • Identify the graph properties required for Topological Sorting (Directed Acyclic Graphs).
  • Calculate the in-degree of vertices to trace Kahn's algorithm for Topological Sort.
  • Trace the Ford-Fulkerson algorithm to find the maximum flow in a network.
  • Identify augmenting paths and bottleneck capacities in a residual graph.

Topological Sorting

Topological Sorting is used to linearly order the vertices of a graph such that for every directed edge U→VU \to V, vertex UU comes before VV in the ordering. This is fundamentally used for dependency resolution (e.g., scheduling tasks, compiling software where library A must be built before library B).

The Strict Constraint: Topological Sorting is only possible in Directed Acyclic Graphs (DAGs).

  • If the graph is undirected, there is no strict dependency.
  • If the graph has a cycle (A depends on B, B depends on C, C depends on A), it creates a deadlock, and sorting is impossible.

Time Complexity: Since it is based on Depth-First Search (DFS) or Breadth-First Search (Kahn's Algorithm), the time complexity is O(V+E)O(V + E).

Trace: Kahn's Algorithm for Topological Sort

  1. 1
    Step 1

    Kahn's algorithm relies on calculating the In-Degree of every vertex (the number of incoming edges). A vertex with an in-degree of 0 has no dependencies and can be processed immediately.

  2. 2
    Step 2
    1. Calculate the in-degree of all vertices.
    2. Enqueue all vertices with an in-degree of 0.
    3. While the queue is not empty:
      • Dequeue a vertex UU and add it to the final sorted output.
      • For every neighbor VV of UU, theoretically 'remove' the edge U→VU \to V by decreasing the in-degree of VV by 1.
      • If the in-degree of VV becomes 0, enqueue VV.
  3. 3
    Step 3

    If the queue becomes empty but the sorted output does not contain all VV vertices, it means the remaining vertices all have an in-degree >0>0. This mathematically proves the graph contains a cycle, and topological sorting has failed.

Network Flow: The Ford-Fulkerson Method

(Directly answers the 7-mark numerical from 2024 Q7b)

In a flow network, edges represent pipes with a specific Capacity. There is a Source (S) that produces infinite flow, and a Sink (T) that absorbs it. The goal is to find the Maximum Flow that can be pushed from S to T without exceeding any pipe's capacity.

Core Rules:

  1. Capacity Constraint: Flow through an edge cannot exceed its capacity.
  2. Flow Conservation: For every node (except S and T), the total incoming flow must exactly equal the total outgoing flow.

Trace: Ford-Fulkerson Max Flow Algorithm

  1. 1
    Step 1

    Consider the exact network from the 2024 Q7b exam:

  2. 2
    Step 2

    We find any path from S to T that still has capacity. Let's take S -> A -> B -> T.

    • The capacities are: SA(10), AB(4), BT(10).
    • The Bottleneck (minimum capacity on this path) is 4.
    • We push 4 units of flow.
    • Residual Capacities left: SA = 6, AB = 0, BT = 6.
    • Max Flow so far: 4.
  3. 3
    Step 3

    We find another path: S -> C -> D -> T.

    • The residual capacities are: SC(10), CD(9), DT(10).
    • The Bottleneck is 9.
    • We push 9 units of flow.
    • Residual Capacities left: SC = 1, CD = 0, DT = 1.
    • Max Flow so far: 4 + 9 = 13.
  4. 4
    Step 4

    Are there any paths left from S to T?

    • S can send to A (6 left) or C (1 left).
    • From A, we can only go to C (2 left) because AB is full (0 left).
    • From C, we cannot go anywhere because CD is full (0 left). Because the pipe C -> D and A -> B are completely bottlenecked, we can no longer reach the Sink T.
  5. 5
    Step 5

    Since no more augmenting paths exist, the algorithm terminates. The Final Maximum Flow Value is 13. (Note: This matches the capacity of the minimum cut through edges AB and CD: 4 + 9 = 13, proving our answer is optimal via the Max-Flow Min-Cut theorem).

Knowledge Check

Question 1 of 3
Q1Single choice

Topological sorting is only possible in:

Previous

Next