Implementing Topological Sort in JavaScript

Topological sort is an algorithm used to find a linear ordering of vertices in a directed acyclic graph (DAG) such that for every directed edge from vertex u to vertex v, u comes before v in the ordering. This is incredibly useful in scheduling tasks with dependencies, resolving compilation order, or ordering courses with prerequisites. Your challenge is to implement this algorithm in JavaScript.

Problem Description

You are tasked with creating a JavaScript function that takes a directed acyclic graph (DAG) as input and returns a list of its vertices in a valid topological order. If the graph contains a cycle (and is therefore not a DAG), your function should indicate this.

Requirements:

• The function should accept the graph representation. A common way to represent a graph is using an adjacency list, where a map (or object) stores each vertex as a key, and its value is an array of vertices that it points to.
• The function should return an array of vertices representing a valid topological order.
• If the graph contains a cycle, the function should return a specific indicator (e.g., null or an empty array, clearly documented in the notes).
• The algorithm should be efficient.

Expected Behavior:

For a given DAG, there might be multiple valid topological sorts. Your implementation should return any one of them. The ordering of nodes with no dependencies between them is flexible.

Edge Cases:

• An empty graph.
• A graph with a single node.
• A graph with disconnected components.
• A graph containing a cycle.

Examples

Example 1:

Input:
graph = {
  'A': ['B', 'C'],
  'B': ['D'],
  'C': ['D', 'E'],
  'D': [],
  'E': []
}

Output:
['A', 'C', 'B', 'E', 'D']

Explanation: In this output, 'A' comes before 'B' and 'C'. 'B' comes before 'D'. 'C' comes before 'D' and 'E'. This satisfies all dependencies. Another valid output could be ['A', 'B', 'C', 'D', 'E'].

Example 2:

Input:
graph = {
  '1': ['2'],
  '2': ['3'],
  '3': ['1'] // Cycle introduced here
}

Output:
null

Explanation: The graph contains a cycle (1 -> 2 -> 3 -> 1). A topological sort is not possible for graphs with cycles.

Example 3:

Input:
graph = {
  '5': [],
  '2': ['3'],
  '3': ['1'],
  '4': ['0', '1'],
  '0': [],
  '1': []
}

Output:
['5', '2', '3', '4', '1', '0']

Explanation: This graph has multiple components. '5' has no outgoing edges and can appear anywhere. '2' must come before '3'. '4' must come before '0' and '1'. '3' must come before '1'. A valid topological sort respecting these is ['5', '2', '3', '4', '1', '0']. Other valid outputs exist.

Constraints

• The graph will consist of nodes represented by strings.
• The adjacency list will only contain valid node names as keys and values.
• The number of nodes in the graph will be between 0 and 1000.
• The number of edges in the graph will be between 0 and 10000.
• Your solution should aim for a time complexity of O(V + E), where V is the number of vertices and E is the number of edges.

Notes

• You can choose either Kahn's algorithm (using in-degrees) or a Depth First Search (DFS) based approach.
• When detecting a cycle using DFS, you'll typically need to keep track of nodes currently in the recursion stack.
• If a cycle is detected, the function should return null.
• For an empty graph, an empty array [] is an acceptable output.