Given a directed acyclic graph, return a valid topological ordering: every node appears before all nodes it points to. To make the answer unique, when several nodes are ready (in-degree 0), pick the lexicographically smallest first.
topologicalOrder(graph)
Input format: directed edges as a,b pairs (a → b). Output the ordering
space-separated.
a,b a,c b,d c,d // → a b c d
x,y // → x y
For every edge A → B, A must appear before B in the output. Edges represent dependencies, and you're lining up nodes so no dependency is violated. Only possible without a directed cycle — a cycle would force some node before and after another, a contradiction. Since the graph is guaranteed a DAG, an ordering always exists; the task is constructing the lexicographically smallest one.
A node can be placed the moment none of its prerequisites remain unplaced — every edge pointing into it already "used up." Track this as in-degree: edges still pointing in, unsatisfied. In-degree 0 means no outstanding prerequisites — safe to output now. Kahn's algorithm: repeatedly remove in-degree-0 nodes; removing a node lowers its neighbors' in-degree, possibly unlocking new zero-in-degree nodes.
A node is only placed after all its prerequisites, since it doesn't join the ready pool until its in-degree hits zero, which only happens after every node with an edge into it has already been output. This enforces the topological property globally, not just locally. Always picking the smallest ready node pins down one specific, deterministic ordering.
def topological_order(graph):
indegree = {}
for node in graph:
if node not in indegree:
indegree[node] = 0
for nxt in graph[node]:
indegree[nxt] = indegree.get(nxt, 0) + 1
# Kahn's algorithm, keeping the ready set sorted so ties break by name.
ready = [node for node in indegree if indegree[node] == 0]
ready.sort()
order = []
while ready:
node = ready.pop(0)
order.append(node)
for nxt in graph.get(node, []):
indegree[nxt] -= 1
if indegree[nxt] == 0:
ready.append(nxt)
ready.sort()
return order
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.