Topological Sort - Which Tasks Should Be Executed First

Birbirine bağımlı olan işleri dikkate alacak şekilde graph'ı sıralar. Graph'ın directed olması gerekir. Açıklaması şöyle.

The minimum spanning tree ensures that your internet traffic gets delivered even when cables break.

Topological sort is used in project planning to decide which tasks should be executed first.

Disjoint sets help you efficiently calculate currency conversions between NxN currencies in linear time

Graph coloring can in theory be used to decide which seats in a cinema should remain free during a infectious disease outbreak.

Detecting strongly connected components helps uncover bot networks spreading misinformation on Facebook and Twitter.

DAGs are used to perform very large computations distributed over thousands of machines in software like Apache Spark and Tensorflow

Graph içinde cycle yani döngüler olmamalı. Yani Directed Acyclic olmalı. Açıklaması şöyle.

For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks. A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG)