Tag Archives: depth-first search

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

Depth-First Search (DFS)

There are two core graph exploring algorithms breadth-first search and depth-first search. Assuming that you already familiar with BFS, so – in this topic I’m going to compare these two algorithms and also I will provide my version of DFS.

The algorithm requires some initial point which will be used as a starting point, from which traversing/searching will go on. Here is a graph and let vertix “A” be a starting point.

DFS

From vertex “A” it goes as far as it possible until it reaches the leaf or it self. Once the vertex that has no successors is reached, it gets back. On the way back, if it meets nodes that were not visited then it traverses them in same way. Visually, the path can be represented as level. Thus, it explores first level, then second and so on. Continue reading Depth-First Search (DFS)