Problem statement:
what is Topological sort in graph data structure & algorithm?
what is Topological sort in graph data structure & algorithm?
Topological sort is an ordering of vertices in a directed acyclic graph [DAG] in which each node comes before all nodes to which it has outgoing edges.
For example:
Consider the course prerequisite structure at universities. A directed edge (v,w) indicates that course v must be completed before course w. Every DAG may have one or more topological orderings. Topological sort is not possible if the graph has a cycle, since for two vertices v & w on the cycle, v precedes w & w precedes v.
No comments:
Post a Comment