Wednesday, October 3, 2018

What do you mean by Topological Sort in graph ?

Problem statement: 
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

How to run standalone mock server on local laptop

 Please download the standalone wiremock server from Direct download section at the bottom of the page.  Download and installation Feel fre...