/* related posts with thumb nails */

Topological sorting:

· In graph theory, a topological sort or topological ordering of a directed acyclic graph (DAG) is a linear ordering of its nodes in which each node comes before all nodes to which it has outbound edges. Every DAG has one or more topological sorts.

· In simple words, a topological ordering is an ordering such that any directed path in DAG traverses vertices in increasing order

· A topological ordering of a digraph is a numbering v1 , …, vn of the vertices such that for every edge (vi , vj), we have i < j

Example: in a course prerequisite digraph, a topological sorting is a sequence that satisfies the prerequisites

Related Topics:


Post a Comment