Strongly connected components refer to connected components in a directed graph, and is useful to simplify a directed graph, for instance, merging all vertices in the same strongly connected components to be a big vertex, could produce a Directed Acyclic Graph (DAG) with less number of vertices. This post documents two well-known algorithms (i.e., Kosaraju’s Algorithm and Tarjan’s Algorithm) that solve the strongly connected component problem.

Topological sorting is an operation performed on Directed Acyclic Graph (DAG) to generate a order of all vertices, so that vertex v would not appear before vertex u if there exists a path from vertex u to vertex v.

Weakly connected components refer to connected components in an undirected graph, also known as friend circle problem. This post documents three common solutions to figure out the number of connected components in graphs.

DFS (Deepth First Search) and BFS (Breadth First Search) are two approaches to traverse tree. It is relatively easy to implement BFS in an iterative manner (with the help of queue). While it is a bit challenging to do DFS without reursion.