Monthly Archives: February 2015

Strongly Connected Components

Another useful application of the depth-first search algorithm, is decomposing of the directed graph into the strongly connected components or SCC. A strongly connected component of the graph is a maximal set of vertices in which there is a path from any vertex to any other vertex in both directions.

scc4

The above directed graph has three strongly connected components. Continue reading Strongly Connected Components

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

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)

Breadth-First Search (BFS)

It’s quite easy to find a node in a binary search tree, but, what if we are dealing with unordered tree or graph? In this case the problem become little bit tricky. Because, graph or tree might be very deep and breadth, directed or undirected or even worse it can be cycled. In such cases we have different searching algorithms that can be applied on graph, one of these algorithms is called Breadth-First Search (BFS).

The algorithm traverses a tree or graph starting from some node, it can be any node in the graph. On the diagram below node “A” will be the starting node.

bfs_2

Farther, the graph can be divided on levels. First level contains starting node, other levels contains child nodes of previous level. The levels in BFS can be illustrated in following way: Continue reading Breadth-First Search (BFS)