In this article, we will look at a famous algorithm in Graph Theory, Tarjan Algorithm . We will also look at an interesting problem related to it, discuss the approach and analyze the complexities. Tarjan’s Algorithm is mainly used to find Strongly Connected Components in a directed graph. A directed graph is a graph made up of a set of vertices connected by edges, where the edges have a direction associated with them. A Strongly Connected Component in a graph is basically a self contained cycle within a directed graph where from each vertex in a given cycle we can reach every other vertex in that cycle. Let us understand this with help of an example, consider this graph: In the above graph, the box A and B show the SCC or Strongly Connected Components of the graph. Let us look at a few terminologies before explaining why the above components are SCC. Back-Edge: So an edge of nodes (u,v) is a Back-Edge, if the edge from u to v has Descendent-Ancestor relationship. The node
This website is about programming knowledge. You can call this blog best programming master.