Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest and Clifford Stein : Chapter 22

The authors discuss different representations of graph such as adjacency list representation and adjacency matrix representation.

The authors then discuss about breadth first search method of graph traversal. A vertex is considered to be discovered the first time it is encountered during search. Given a graph $ G = (V, E) $ and a source vertex $s$, BFS produces a "breadth-first-tree" with root s that contains all vertices reachable from $s$. The algorithm discovers all the vertices at distance $k$ from $s$ before discovering any vertices at distance $k+1$. When a vertex $v$ is first discovered in the course of scanning the adjacency list of an already discovered vertex $u$, $u$ is called the predecessor or parent vertex of $v$. The authors provide definitions for shortest path and shortest path distance. The authors then prove some properties of BFS and BFS trees.

The authors then discuss about depth first search method of graph traversal. A vertex is considered finished when its adjacency list has been examined completely. The authors describe the parenthesis structure of discovered and finished time, i.e. if the discovered time is represented with left parenthesis and finished time is represented with right parenthesis, the history of times create a well-formed expression. The authors prove some properties of DFS.

The authors discuss about topological sort of a directed acyclic graph (DAG) $ G = (V, E) $, which is a linear ordering of all its vertices such that if G contains an edge $ (u, v) $ then $u$ appears before $v$ in the ordering. The authors then provide an algorithm to generate topological-sort of a DAG and prove that the algorithm takes $ \Theta(V+E) $ time.

The authors then discuss strongly connected components of a directed graph. The strongly connected component of a directed graph $ G = (V,E) $ is a maximal set of vertices $ C \subseteq V $ such that for every pair of vertices $u$ and $v$ in $C$, we have both $u \leadsto v$ and $v \leadsto u$, i.e. vertices $u$ and $v$ are reachable from each other. The authors then prove some properties of strongly-connected-components.