Tag Archives: Tarjan’s algorithm

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

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