Chapter 3: Graphs

This chapter was very easy to read, and I would score it about a 7 on a scale from 1-10 on readability. This section defined graphs and outlined some common uses for them. A graph is made up of a collection V of nodes and a collection E of edges, which “joins” two of the nodes. Edges represent a symmetric relationship between their ends. Directed graphs are used for asymmetric relationships and contain a set of nodes V and a set of directed edges E'. Each element n E' is an ordered pair, (u, v). u is the tail of the edge and v is the head of the edge. Edge e' leaves node u and enters node v. If a graph is not directed, it is considered an undirected graph, and it is written as a set of nodes {u, v}.

There countless applications of graphs. The book lists five useful applications of graphs and what they can represent: transportation networks, communication networks, information networks, social networks, and dependency networks.

There are several other terms regarding graphs that were defined in this chapter. A path is a sequence P of nodes where each consecutive pair is joined by an edge in G. A path is simple if all of its vertices are distinct from one another. A cycle is a path where the sequence of nodes “cycles back” to where it began. The sequence of nodes in the path or cycle must respect the directionality of edges. A connected graph is a graph where every pair of nodes u and v has a path from u to v. It 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. Furthermore, an undirected graph is considered a tree if it is connected and does not contain a cycle and is the simplest kind of connected graph. Trees can be used to represent a hierarchy.

This section discussed two main methods to determine if there is a path from the starting node, s, to another node, t, in graph G. This is known as s-t connectivity. This section reinforced what I had learned not only in class but what we had done in CS 112. Overall, on a scale from 1-10 regarding readability, this section was about a 7.

The first main method to determining connectivity is the Breadth-First Search (BFS). This method goes outward from s in all possible directions, adding nodes one “layer” at a time. It can only visit nodes that s can reach. The layer that the node is indicates the point in time the node is reached, and therefore the distance between s and t. There is only a path from s to t if and only if t appears in one of the layers. This BFS will result in a tree, T, rooted at s, called a BFS tree. Only nodes reachable from s can be added to T, therefore, this allows us to answer the connectivity question.

The second method to determining connectivity is the Depth-First Search (DFS). The way I am able to best distinguish BFS from DFS is to think of DFS as the way to solve a maze. You start at s and take the first edge leading out, continuing until a dead-end is reached. In general, DFS explores G by going as deep as possible and only retracing when necessary. Because of this functionality, DFS must maintain global knowledge of which nodes have already been explored.