Showing posts with label graph. Show all posts
Showing posts with label graph. Show all posts

Wednesday, October 3, 2018

What are the applications of Topological Sorting in graph?

Problem statement: 
what are the uses of Topological Sorting in graph?
  1. Representing course prerequisites
  2. In detecting deadlocks
  3. Evaluating formulae in spreadsheet
  4. Pipeline of computing jobs
  5. Checking for symbolic link loop

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.

Blueprint for self-improvement

To learn faster: Make the process fun To understand yourself : Write To understand the world better : Read To build deeper connection : Lis...