Chapter 3.5: Connectivity in Directed Graphs

In order to represent a directed graph, it is best to use an adjacency lists. Each node can have 2 lists associated with it: a list of nodes it points to and a list of nodes that point to it. Graph search algorithms (BFS & DFS) are basically the same for a directed graph as they are for an undirected graph. BFS starts at a node s and works outwardly, in the same way it would for an undirected graph. The algorithm still runs in O(n+m) time. However, BFS computes the set of all nodes for which there is a path from s to a node t, and this doesn't run both ways. There may or may not be a path from a node t back to s. DFS runs similarly.

A directed graph is strongly connected if for every two nodes u and v, there is a path from u to v and a path from v to u. When there is a path from u to v and a path from v to u, we can call nodes u and v mutually reachable. So a graph is strongly connected if every pair of nodes is mutually reachable.

If u and v are mutually reachable and v and w are mutually reachable, then v and w are mutually reachable.

In a directed graph, the strong component is the set of all v such that s and v are mutually reachable. For any two nodes s and t in a directed graph, their strong components are either identical or disjoint.

I'd rate this section a 10! It was very easy to read and understand.