**__3.5: Connectivity in Directed Graphs__**

An example of a directed graph is the world wide web, nodes are pages and edges are hyperlinks.  

**Representing Directed Graphs**

A directed graph has each node with two lists associated with it: one list consists of nodes to which it has edges, and a second list consists of nodes from which it has edges.  

**The Graph Search Algorithms**

Directed graphs still have a search runtime of O(n+m).

**Strong Connectivity**

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.  In addition, two nodes u and v in a directed graph are //mutually reachable// if there is a path from u to v and also a path from v to u.  If u and v are mutually reachable, and v and w are mutually reachable, then u and w are mutually reachable.  

The strong component containing a node s in a directed graph to be 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.  

This section lays out directed graphs and connectivity.  8.5/10.