Tag Archives: Topological sort

Topological Sort

Besides, traversing and searching shortest path in a graph, you can sort vertices in directed acyclic graph. This type of sorting is called topological sort and it can be useful in task scheduling application. The tasks can have dependencies on other tasks. These dependencies can be simple, then we can arrange the tasks in a linked list and execute task one by one. In case if we have more that one dependency, then we will use DAG, to represent these tasks.

gag_toposort

The topological sorting can be applied only on DAG, because cycle doesn’t give a chance to prioritize tasks. Continue reading Topological Sort

Detecting a Cycle in a Graph

Detecting a Cycle in a Graph is one of the core problems. First, let’s have a look at what types of cycles can occur in a graph. Generally, we can distinguish two types of graph: directed and undirected. Thus, the cycle also can be directed and undirected.

cycles_1

Directed graph that has no cycles is called directed acyclic graph or DAG. Continue reading Detecting a Cycle in a Graph