Friday, July 8, 2016

Topological Sorting For DAG and its Applications

Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering. Topological Sorting for a graph is not possible if the graph is not a DAG. 
http://www.geeksforgeeks.org/topological-sorting/

Applications:
1. Shortest Path in Directed Acyclic Graph:
http://www.geeksforgeeks.org/shortest-path-for-directed-acyclic-graphs/

2. Longest Path in a Directed Acyclic Graph
http://www.geeksforgeeks.org/find-longest-path-directed-acyclic-graph/

3.Find Itinerary from a given list of tickets
http://www.geeksforgeeks.org/find-itinerary-from-a-given-list-of-tickets/

4.Find the minimum cost to reach destination using a train
http://www.geeksforgeeks.org/find-the-minimum-cost-to-reach-a-destination-where-every-station-is-connected-in-one-direction/


5.

No comments:

Post a Comment