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.