Section 3.5 This section discussed the concept of connectivity in directed graphs. Directed graphs are distinct from undirected graphs because instead of a node having a list of connected nodes, each node has two lists – one with nodes to which it has edges and one with nodes from which it has edges. We can traverse a directed graph using BFS or DFS, similar to the way we use them to search undirected graphs with the same running time: O(m+n). The main thing to remember is that these searches are only returning paths in one direction, for instance, the path from s to t, but not necessarily the paths from t to s, which might not exist. A graph is strongly connected if for every two nodes there is a path from u to v and a path from v to u, which also means the two points are mutually reachable (Proof p. 98). From the proof in the book, we arrive at a strong component, which contains a node s in a directed graph to be the set of all v such that s and v are mutually reachable (p.99). We can find the strong component by running BFS twice, in reverse on the second round. I would give this section a 10—the concept of connectivity in directed graphs was explained pretty logically and I feel good about my understanding of it. The slides with visuals from class also reinforced my understanding.

Section 3.6 This section reviewed directed acyclic graphs and topological ordering. A directed acyclic graph is any directed graph that contains no cycles. We can use DAGs to represent precedence relations or dependencies – anything with a hierarchical ordering, I think. A topological ordering is “an ordering of [graph G’s] nodes as v1, v2, …, vn so that for every edge (vi, vj) we have i<j. In other words, all edges points ‘forward.’” The proof on p. 101 shows that if a graph has a topological ordering, then it must be a DAG. On p. 102 it proves the converse of this, that if a graph is a DAG then it has a topological ordering (I didn’t quite understand this proof as well… does this mean that all DAGs have topological ordering and all topological graphs are DAGs simultaneously? Do you ever have a DAG without topological ordering, or is that pretty much a general term for all ordering in DAGs?). The running time of the algorithm that corresponds to this proof has a running time of O(n^2), which can be reduced to O(m+n) if we delete the nodes that don’t have incoming edges as we encounter them. I give this chapter an 8 for readability – I understand conceptually what topological ordering and acyclic graphs are, but the proofs were kind of confusing for some reason.