Topological Sort Implementation

Topological sort is an algorithm used to order nodes in a directed acyclic graph (DAG) such that for every directed edge from node A to node B, node A comes before node B in the ordering. This is incredibly useful in scenarios like dependency resolution (e.g., compiling software, building a project) or scheduling tasks where certain tasks must be completed before others. Your task is to implement a topological sort algorithm in JavaScript.

Problem Description

You are given a directed acyclic graph represented as an adjacency list. The adjacency list is a JavaScript object where keys are nodes and values are arrays of nodes that the key node points to. Your goal is to implement a function topologicalSort(graph) that returns a valid topological ordering of the nodes in the graph.

What needs to be achieved:

• The function should take an adjacency list representing a DAG as input.
• The function should return an array containing the nodes in a valid topological order.
• If the graph is not a DAG (i.e., contains cycles), the function should return null.

Key Requirements:

• The algorithm must correctly order the nodes such that all dependencies are satisfied.
• The algorithm should handle disconnected graphs correctly (i.e., graphs with multiple components).
• The algorithm must detect cycles and return null if a cycle is found.

Expected Behavior:

The function should return an array of nodes in topological order. The order may not be unique, but it must be a valid topological order. If a cycle is detected, the function should return null.

Edge Cases to Consider:

• Empty graph (no nodes or edges).
• Graph with a single node.
• Graph with multiple disconnected components.
• Graph with cycles.
• Nodes represented by strings or numbers.

Examples

Example 1:

Input: {
  'A': ['B', 'C'],
  'B': ['D'],
  'C': ['D'],
  'D': []
}
Output: ['A', 'C', 'B', 'D']  (or ['A', 'B', 'C', 'D'])
Explanation: 'A' must come before 'B' and 'C', 'B' must come before 'D', and 'C' must come before 'D'.  Therefore, a valid order is A -> C -> B -> D.

Example 2:

Input: {
  'A': ['B'],
  'B': ['C'],
  'C': ['A']
}
Output: null
Explanation: This graph contains a cycle (A -> B -> C -> A), so a topological sort is not possible.

Example 3:

Input: {
  'A': ['B'],
  'B': [],
  'C': ['D'],
  'D': []
}
Output: ['C', 'D', 'A', 'B'] (or any other valid order of the components)
Explanation: This graph has two disconnected components: {A, B} and {C, D}.  A valid topological sort would order the nodes within each component and then combine the components in any order.

Constraints

• The graph will be represented as an object (adjacency list).
• Nodes will be represented as strings or numbers.
• The graph will contain at most 1000 nodes.
• The graph will contain at most 10000 edges.
• The algorithm should have a time complexity of O(V + E), where V is the number of vertices (nodes) and E is the number of edges.

Notes

• Consider using Depth-First Search (DFS) to implement the topological sort.
• Keep track of visited nodes and nodes currently in the recursion stack to detect cycles.
• The order of nodes in the output array is not strictly defined; any valid topological order is acceptable.
• Remember to handle disconnected graphs correctly by iterating through all nodes in the graph.
• A common approach is to use a stack to store the nodes in topological order as they are visited during the DFS traversal.