Order dependencies without inventing an order for cycles

Try

Suppose tasks A and B must both precede C. The orders A,B,C and B,A,C both respect the dependencies. A topological ordering need not be unique; it is any linear order placing the tail of every directed edge before its head.

Predict

Predict why a directed cycle prevents such an order. A→B→C→A would require A before itself by transitivity. A DAG is a directed acyclic graph. Indegree counts incoming edges; outdegree counts outgoing ones.

Experiment

Use the small dependency diagram. Repeatedly choose an indegree-zero remaining vertex, record it and remove its outgoing edges. Track indegrees after each removal. Then add a reverse edge that creates a cycle and determine where the process becomes stuck.

Understand

Worked source proof: every nonempty finite DAG has a source, a vertex with indegree zero. If not, follow a predecessor from each vertex indefinitely. A repeated vertex must eventually occur, yielding a directed cycle, contradiction. This existence theorem justifies each step of Kahn’s algorithm.

When a source is removed, every incoming predecessor has already been recorded, so no edge points backward in the final order. If a nonempty remainder has no source, the same predecessor argument certifies a cycle there. Empty completion is success; a partial order of removed vertices is not a full answer.

Invalid inference: a cycle in the undirected drawing forbids topological ordering. Directed orientation matters; a triangle A→B,A→C,B→C is acyclic.

Apply

Specify the edge direction as prerequisite-to-dependent or another stated convention. Check every edge against a proposed ordering. Different valid source choices may produce different correct orders, so tests should not demand one arbitrary order.

Continue

Depth: a partial order can be represented by a DAG with redundant transitive edges omitted or included. Topological sorting resolves precedence but does not by itself optimize elapsed time, resource use or parallel scheduling.