leetcode topological sort

3 min read 19-10-2024

Mastering Topological Sort: A Guide for LeetCode Conquerors

Topological sort, a fundamental graph algorithm, finds its way into many LeetCode problems, often disguised as course schedules, task dependencies, or even alien language ordering. This article will equip you with the knowledge and tools to confidently tackle these problems, using insights and explanations from GitHub discussions.

Understanding Topological Sort

Imagine you're building a house. You need to lay the foundation before you can frame the walls, and the roof comes last. Topological sort is like the construction manager, providing a linear ordering of tasks or elements where each element depends on its predecessors.

Here's the catch:

Directed Acyclic Graph (DAG): Topological sort only works on DAGs, graphs with directed edges and no cycles. Imagine trying to build the roof before the walls - that's a cycle, and it breaks the logical order!

Techniques for Topological Sort

Two popular techniques dominate the LeetCode landscape:

1. Depth-First Search (DFS) with Kahn's Algorithm:

DFS: This algorithm explores the graph recursively, marking visited nodes.
Kahn's Algorithm: It iteratively selects nodes with no incoming edges, adds them to the sorted order, and removes their outgoing edges. This process repeats until all nodes are processed.

Let's break it down with an example from LeetCode:

Problem: Course Schedule (https://leetcode.com/problems/course-schedule/)

Explanation:

Input: A list of courses and prerequisites, represented as edges in a graph.
Output: Can all courses be completed in a valid order? If so, return that order.

Code Snippet (GitHub):

def canFinish(numCourses, prerequisites):
  """
  Returns True if all courses can be finished, and False otherwise.
  """
  graph = [[] for _ in range(numCourses)]
  indegree = [0 for _ in range(numCourses)]

  # Build the graph and calculate indegree
  for course, pre in prerequisites:
    graph[pre].append(course)
    indegree[course] += 1

  queue = [i for i in range(numCourses) if indegree[i] == 0]

  count = 0
  while queue:
    node = queue.pop(0)
    count += 1
    for neighbor in graph[node]:
      indegree[neighbor] -= 1
      if indegree[neighbor] == 0:
        queue.append(neighbor)

  return count == numCourses

# Example Usage
numCourses = 2
prerequisites = [[1,0]]
print(canFinish(numCourses, prerequisites)) # Output: True

2. Depth-First Search with Topological Ordering:

DFS: This approach uses recursion to traverse the graph.
Topological Ordering: During the DFS, nodes are added to the result in reverse post-order, which ensures that each node is added after all its dependencies.

GitHub Example:

def topological_sort(graph):
  """
  Returns a topological ordering of the graph.
  """
  result = []
  visited = set()
  def dfs(node):
    visited.add(node)
    for neighbor in graph[node]:
      if neighbor not in visited:
        dfs(neighbor)
    result.append(node)

  for node in range(len(graph)):
    if node not in visited:
      dfs(node)

  return result[::-1]

# Example Usage
graph = {
  0: [1, 2],
  1: [3],
  2: [3],
  3: []
}
print(topological_sort(graph)) # Output: [0, 1, 2, 3]

Key Considerations:

Cycle Detection: Be mindful of cycles. If a cycle exists, you cannot obtain a valid topological order.
Multiple Solutions: Multiple valid topological orderings may exist for a given DAG.
Efficiency: Both techniques generally have a time complexity of O(V + E), where V is the number of vertices and E is the number of edges.

LeetCode Practice:

Course Schedule: A classic problem that introduces the concept of topological sort in the context of course dependencies.
Alien Dictionary: Finds the lexicographical order of an alien language based on word pairs.
Task Scheduling Order: Determines the order in which tasks can be completed based on dependencies.

Conclusion

Topological sort is a powerful tool for navigating dependency relationships within graphs. By understanding its core principles and practicing with LeetCode problems, you'll gain valuable insights into graph algorithms and improve your problem-solving skills.

Remember: The code snippets provided here are based on examples from GitHub repositories and might require modifications based on the specific problem you're tackling. Always analyze the problem requirements carefully, and leverage the insights from the provided examples to craft your solution.