A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.

Topological Sorting and Ordering

Research Depth 228 in the knowledge graph ☐ I know this ☆ Set as goal

3topics build on this

1,351prerequisites beneath it

Directed Acyclic Graphs for Causal Modeling Directed Graphs and Digraphs +1 more→→Cycle Detection in Directed Graphs Divide-and-Conquer Recurrences and the Master Theorem

Core Idea

Topological sorting arranges vertices of a directed acyclic graph (DAG) in a linear order such that for every directed edge from u to v, u comes before v. This ordering is useful for scheduling tasks with dependencies, resolving symbol dependencies in compilers, and determining precedence.

Explainer

You already know that a directed acyclic graph (DAG) models dependencies: an edge from u to v means "u must come before v." A topological sort turns that partial ordering into a total ordering — a single linear sequence where all the "must come before" constraints are respected. The everyday analogy is a college degree plan: courses have prerequisites, and a valid course schedule is a topological sort of the prerequisite DAG.

The key reason topological sorts only exist for DAGs is intuitive: if the graph contained a directed cycle (A → B → C → A), then A would need to come before itself, which is impossible in any linear order. This makes cycle detection a natural companion to topological sorting — if you try to sort a graph and fail, you've found a cycle.

There are two standard algorithms. Kahn's algorithm works by repeatedly identifying vertices with no incoming edges (no remaining prerequisites) and removing them one at a time, adding each to the output sequence. Any vertex with in-degree 0 is "safe to go first" given what remains. When you remove a vertex, you decrement the in-degrees of its neighbors, potentially freeing them up next. If the graph is a DAG, this process empties it; if a cycle exists, some vertices will never reach in-degree 0.

The second approach uses depth-first search: run DFS on the graph, and each time you *finish* exploring a vertex (all its descendants are done), prepend it to the output list. The result is a valid topological order because finishing u after all of u's successors means u naturally lands before all of them when the list is reversed. This DFS-based approach is the foundation of the next topic in this sequence and appears in many advanced graph algorithms. Both methods run in O(V + E) time, making topological sort efficient even on large dependency graphs.

Practice Questions 5 questions

Prerequisite Chain

Understanding Zero → The Number Zero → Counting to Five → Counting to 10 → One-to-One Correspondence → Counting a Set of Objects Up to 20 → Cardinality: The Last Number Counted → Matching Numerals to Quantities → Subitizing Small Quantities → Addition Within 10 → Making 10 as an Addition Strategy → Addition Within 20 → Doubles and Near Doubles → Doubles Facts Within 10 → Near Doubles Facts Within 20 → Mental Math Strategies for Addition → Mental Math: Adding and Subtracting Tens → Addition Within 100 → Repeated Addition as Multiplication → Multiplication as Equal Groups → Multiplication: Arrays → Basic Multiplication Facts (0s, 1s, 2s, 5s, 10s) → Multiplication Facts Within 100 → Division as Equal Sharing → Division as Grouping (Measurement Division) → Division: Grouping (Repeated Subtraction) Model → Division: Fair Sharing Model → Division as Equal Sharing → Division as Grouping → Basic Division Facts → Division Facts Within 100 → Multiplication and Division Fact Families → Relationship Between Multiplication and Division → Division Facts as Inverse of Multiplication → Remainders and Quotients in Division → Division Word Problems → Multi-Step Word Problems → Solving Multi-Step Word Problems → Multiplication Word Problems → Division Word Problems → Introduction to Long Division → Factors and Multiples → Prime and Composite Numbers → Equivalent Fractions → Relating Fractions and Decimals → Decimal Place Value → Integers and the Number Line → Comparing and Ordering Integers → Absolute Value → Adding Integers → Subtracting Integers → Multiplying Integers → Dividing Integers → Unit Rates → Proportions → Percent Concept → Converting Between Fractions, Decimals, and Percents → Operations with Rational Numbers → Two-Step Equations → Solving Multi-Step Equations → Equations with Variables on Both Sides → Angle Pairs: Complementary, Supplementary, and Vertical → Parallel Lines and Transversals → Corresponding Angles → Alternate Interior Angles → Triangle Angle Sum Theorem → Exterior Angle Theorem → Triangle Inequality Theorem → Similar Triangles: AA Similarity → Similar Triangles: SSS and SAS Similarity → Proportions in Similar Triangles → Right Triangle Trigonometry Introduction → Sine, Cosine, and Tangent Ratios → Trigonometric Ratios Review → Radian Measure → Converting Between Degrees and Radians → The Unit Circle → Graphing Sine and Cosine → Graphing Tangent and Reciprocal Trigonometric Functions → Derivatives of Trigonometric Functions → Antiderivatives → Iterated Integrals and Fubini's Theorem → Double Integrals in Cartesian Coordinates → Double Integrals in Polar Coordinates → Double Integrals in Polar Coordinates → Double Integrals: Definition and Setup → Iterated Integrals and Fubini's Theorem → Double Integrals over Rectangular Regions → Double Integrals over General Regions → Applications of Double Integrals: Area, Mass, and Moments → Triple Integrals in Cartesian Coordinates → Triple Integrals in Cylindrical and Spherical Coordinates → Change of Variables and the Jacobian Determinant → Applications of Triple Integrals: Volume and Mass → Vector Fields and Their Representations → Line Integrals of Vector Fields → Work and Circulation → Line Integrals of Scalar and Vector Functions → Fundamental Theorem for Line Integrals → Conservative Vector Fields → Conservative Vector Fields and Potential Functions → Curl and Divergence of Vector Fields → Curl and Divergence → Divergence Theorem → Electric Flux and Divergence Theorem → Gauss's Law: Integral Form and Meaning → Solving Problems with Gauss's Law → Conductors in Electrostatic Equilibrium → Capacitance and Capacitors → Dielectrics → Dielectric Constant and Relative Permittivity → Electric Field Inside Dielectric Materials → Dielectric Materials and Polarization → Dielectric Susceptibility and Permittivity → Energy Density in Electric Fields → Electric Current and Current Density → Electrical Resistance and Resistivity → Ohm's Law and Circuit Elements → Electromotive Force (EMF) and Batteries → Kirchhoff's Circuit Laws: Voltage and Current → DC Circuit Network Analysis Methods → Transient Response in RC Circuits → RC Circuits → LC and RLC Circuits → AC Circuits: Fundamentals → Impedance and Reactance → AC Power and Resonance → Electromagnetic Waves → Postulates of Special Relativity → Time Dilation → Length Contraction → Lorentz Transformation → Relativistic Velocity Addition → Relativistic Momentum and Energy → Mass-Energy Equivalence and E=mc² → Photons as Particles with Energy and Momentum → Planck-Einstein Relation: Energy and Frequency → Photoelectric Effect → The Photon: Light as Quanta → Compton Scattering → Wave-Particle Duality → de Broglie Wavelength → The Schrödinger Equation → State Vectors and Wavefunctions → Quantum Superposition → The Measurement Problem → Interpretations of Quantum Mechanics → Postulates of Quantum Mechanics → Observables and Quantum Operators → Commutators and Commutation Relations → Quantum Angular Momentum → Quantum Mechanical Treatment of Hydrogen → Solving the Schrödinger Equation for Hydrogen Atom → Quantum Numbers → Electron Configuration → Periodic Trends → Covalent Bonding → Electronegativity and Bond Polarity → Ionic Bonding → Lewis Structures → VSEPR Theory and Molecular Geometry → Molecular Geometry and Electron Pair Geometry → Molecular Polarity and Dipole Moments → Intermolecular Forces → States of Matter and Phase Changes: Melting, Boiling, and Sublimation → Gas Laws and the Ideal Gas Equation → Gas Stoichiometry and Volume-Volume Calculations → Thermochemistry and Enthalpy → Heat Capacity and Calorimetry → Entropy and Molecular Disorder → Spontaneity and ΔG → Entropy and Gibbs Free Energy → Chemical Equilibrium → Acid-Base Chemistry → Weak Acid Ionization → Weak Base Ionization → Acid and Base Strength: Ka, Kb, and Ionization → Leaving Groups and Nucleofugality → SN2 Substitution Reactions → SN1 Substitution Reactions → E1 Elimination Reactions → Alcohols and Ethers: Structure, Properties, and Nomenclature → Reactions of Alcohols → Aldehydes and Ketones: Structure and Reactivity → Oxidation Reactions in Organic Chemistry → Oxidation of Alcohols to Aldehydes and Ketones → Aldehyde and Ketone Structure and Nomenclature → Nucleophilic Addition to Aldehydes and Ketones → Carboxylic Acids and Their Derivatives → IUPAC Nomenclature of Carbonyls and Carboxylic Acids → IUPAC Nomenclature of Alkenes → Electrophilic Addition to Alkenes → Aromaticity and Benzene → Electrophilic Aromatic Substitution (EAS) → Nucleophilic Aromatic Substitution (SNAr) → Nucleophilic Acyl Substitution → Amines: Structure, Basicity, and Reactions → Amine Reactivity: Nucleophilicity and Basicity → Amino Acid Structure and Properties → Peptide Bonds and Polypeptide Formation → Protein Primary Structure → Protein Secondary Structure → Protein Tertiary Structure → Enzyme Structure and Function → Transcription: DNA to RNA → RNA Types and Structure → RNA Structure and Intramolecular Base Pairing → RNA Processing and Splicing → Translation: RNA to Protein → Ribosomes: Protein Synthesis Machines → Translation: Initiation and Elongation → Post-Translational Modifications → Proteasomal Degradation and Ubiquitin-Mediated Marking → Cell Cycle Regulation and Checkpoints → Cell Cycle Checkpoints: Ensuring Genome Integrity → Cell Cycle Checkpoints and Cancer Prevention → Mitotic Spindle Checkpoint and Chromosome Segregation → Kinetochore Structure and Function → Mitochondria: Structure and Function → Cellular Respiration Overview → Bacterial Metabolism Overview → Antibiotic Resistance Mechanisms → Infectious Disease Epidemiology → Foundations of Epidemiology → Measuring Disease Frequency: Incidence and Prevalence → Epidemiologic Study Designs → Confounding: Definition, Identification, and Causal Criteria → Directed Acyclic Graphs for Causal Modeling → Topological Sorting and Ordering

Longest path: 229 steps · 1351 total prerequisite topics

Prerequisites (3)

Directed Graphs and Digraphshard Directed Acyclic Graphs for Causal Modelinghard Depth-First Search (DFS)soft

Leads To (2)

Cycle Detection in Directed Graphssoft Divide-and-Conquer Recurrences and the Master Theoremsoft