Topological sorting

In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, a topological sort or topological ordering of a <a href="/facts/Directed_graph/YBdfQ0um">directed graph</a> is a <a href="/facts/Total_order/xnTtmuYJ">linear ordering</a> of its <a href="/facts/Vertex_(graph_theory)/WhlWmL3o">vertices</a> such that for every directed edge (u,v) from vertex u to vertex v, u comes before v in the ordering. For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks. Precisely, a topological sort is a graph traversal in which each node v is visited only after all its dependencies are visited. A topological ordering is possible if and only if the graph has no <a href="/facts/Directed_cycle/Is44edrv">directed cycles</a>, that is, if it is a <a href="/facts/Directed_acyclic_graph/k6zq1os9">directed acyclic graph</a> (DAG). Any DAG has at least one topological ordering, and there are <a href="/facts/Linear_time/77T62gmf">linear time</a> <a href="/facts/Algorithm/fnl5NmRt">algorithms</a> for constructing it. Topological sorting has many applications, especially in ranking problems such as <a href="/facts/Feedback_arc_set/p69AScPL">feedback arc set</a>. Topological sorting is also possible when the DAG has <a href="/facts/Connectivity_(graph_theory)/FSNjsYhz">disconnected components</a>.

Topological sorting open-in-new

Topological sorting