3.5 Connectivity in Directed Graphs

In a directed graph, an edge (u,v) has a direction: from u to v or from v to u. The nodes in these kinds of edges are in asymmetric relations. A World Wide Web is an easy example of a directed graph as one cannot follow the links in reverse order or even the fact that some websites links to other websites which don't necessarily link back to the first websites.In representing directed graphs, each node has 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.We still use BFS and DFS as graph search algorithms with some differences. When using BFS for directed graphs, it is possible for a node s to have a path to a node t even though t has no path to s since the relation is asymmetric: BFS is here computing the set of all nodes t with the property that s has a path to t. Such nodes may or may not have paths back to s. For DFS, the same procedure happens as in an undirected graph, except that now it follows the nodes' directions: when DFS is at a node u, it recursively launches a DFS in order for each node to which u has an edge.Both of the implementations still run in linear time(O(m+n)).

Two nodes u and v in a directed graph are mutually reachable if there is a path from u to v and a path from v to u. In this case, the two nodes are also said to be strongly connected. If u and v are mutually reachable and v and w are mutually reachable, then u and w are mutually reachable. A strong component is a set of all v such that s and v are mutually reachable. The strong components for all nodes can be computed in O(m+n) time.For any two nodes s and t in a directed graph, their strong components are either identical or disjoint.

This section was short and interesting. I give it an 8/10 since it didn't gave too much information.