Description

This PR implements Topological Sorting using Depth-First Search (DFS) for Directed Acyclic Graphs (DAGs) as requested in issue#6938.

Changes Made

• ✅ ImplementedTopologicalSortDFS.java with DFS-based topological sorting algorithm
• ✅ Added cycle detection using recursion stack to validate DAG property
• ✅ Created comprehensive test suite (TopologicalSortDFSTest.java) with 20+ test cases
• ✅ Added practical examples (TopologicalSortExample.java) demonstrating real-world usage
• ✅ Included complete Javadoc documentation for all methods

Algorithm Details

• Approach: DFS traversal with visited array and recursion stack for cycle detection
• Time Complexity: O(V + E) where V = number of vertices, E = number of edges
• Space Complexity: O(V) for recursion stack and auxiliary data structures
• Key Features:
  • Detects cycles and throwsIllegalArgumentException for non-DAG graphs
  • Handles disconnected components correctly
  • IncludesisDAG() utility method for graph validation

Implementation Highlights

1. Cycle Detection: Uses recursion stack to accurately detect back edges
2. Adjacency List: Efficient graph representation usingList<List<Integer>>
3. Stack-based Ordering: Pushes vertices to stack after DFS completion for correct topological order
4. Edge Case Handling: Properly handles empty graphs, single vertices, and null inputs

Test Coverage

The test suite includes comprehensive coverage for:

• ✅ Simple and complex DAGs with multiple dependencies
• ✅ Linear graphs and disconnected components
• ✅ Cycle detection (self-loops, simple cycles, complex cycles)
• ✅ Edge cases (empty graph, single vertex, null input)
• ✅ Real-world scenarios:
  • Task scheduling with dependencies
  • Course prerequisite ordering
  • Build system dependency resolution

Example Usage