Topological Sorting Overview

Overview

This lecture explains topological sorting, its application to Directed Acyclic Graphs (DAGs), and how to implement topological sort using Depth First Search (DFS).

Topological Sorting Basics

• Topological sorting is a linear ordering of vertices in a directed acyclic graph (DAG).
• For every directed edge u → v, u must appear before v in the ordering.
• Topological sorting is only possible for DAGs, not for graphs with cycles or undirected graphs.
• Multiple valid topological orderings may exist for a given DAG.

Why Only DAGs?

• In undirected graphs, edges go both ways, making the required ordering impossible.
• In directed graphs with cycles, cyclic dependencies prevent a consistent ordering as required by definition.

DFS-Based Topological Sort Algorithm

• Use a visited array to keep track of visited nodes, initialized as unvisited (zero).
• Use a stack to store the ordering of nodes following the Last-In-First-Out (LIFO) principle.
• Iterate through each node; if it is unvisited, perform DFS from that node.
• During DFS: mark the node as visited, recursively call DFS for all unvisited adjacent nodes.
• After all adjacent nodes are visited, push the current node onto the stack.
• Once DFS is complete for all nodes, pop nodes from the stack to get the topological ordering.

Example Walkthrough

• Given edges: 5→0, 4→0, 5→2, 2→3, 3→1, 4→1, the stack after DFS includes nodes in one valid topological order: 5, 4, 2, 3, 1, 0.
• Popping from the stack gives one valid topological sorting.

Algorithm Code Structure

• Declare and initialize the visited array and stack.
• For each vertex, if not visited, call DFS.
• In DFS: mark visited, recursively visit adjacent nodes, push node to stack after visiting all adjacents.
• After DFS, pop elements from the stack into a result array for final ordering.
• Time complexity: O(V + E). Space complexity: O(V).

Intuition Behind the Algorithm

• Nodes are stacked only after all their dependencies (adjacent nodes) are processed.
• This ensures dependencies are respected in the final ordering.
• On reversing the stack, each node appears after its dependencies, maintaining the required order.

Key Terms & Definitions

• Directed Acyclic Graph (DAG) — A directed graph with no cycles.
• Topological Sorting — Linear ordering where for every edge u → v, u appears before v.
• DFS (Depth First Search) — Graph traversal technique that explores as far as possible along each branch.
• Stack — Data structure following Last-In-First-Out (LIFO) order.

Action Items / Next Steps

• Review the DFS algorithm and stack data structure.
• Practice implementing topological sort using DFS on sample DAGs.
• Understand time and space complexity analysis for graph algorithms.