In a directed graph, every edge(u,v) has a direction from u to v. This relationship is asymmetric, and this affects the structure of the resulting graph. An example would be the World Wide Web(the act of browsing from one webpage to another)– where it is hard to browse backwards. Representation. We use an adjacency list representation that we employed for undirected graphs but each node has two lists– one that contains edges to which it reaches from it and the other list contains edges that get to it. The Graph Search Algorithms. BFS and DFS works similarly with directed graphs as they do in undirected graphs. Start with node s, define first layer of nodes to consist of all those to which s has an edge, define a second layer to consist of all additional nodes to which the first layer nodes have an edge. In this way we discover nodes by layer and nodes i layer j are j distance from s. This will also result into a running time of O(m+n). In a directed graph, it is possible to have a path from s to t but not the other way. DFS also works the same way it does with undirected graphs, it explores deeply following edges according to their inherent direction. Strong connectivity. A directed graph is only strongly connected if, for every two nodes are mutually reachable. Proof on Page 98. For any two nodes s and t in a directed graph, their strong components are either identical or disjoint. Its proof is also on page 99.

This section was pretty understandable and I give it a 9/10.