Chapter 3

Chapter 3 delves into the world of graphs, and this section lays down the framework for more advanced discussion and uses. As defined previously, a graph is a means of encoding relationships between pairs of elements. It does this by tracking vertices, elements, and edges, connections between pairs of elements. Edges typically denote a symmetric relationship, but directed graphs denote one way relationships. Transportation networks, communications networks, information networks, social networks, and dependency networks are given as some example use cases of a graph. A particularly important aspect of a graph is determining paths, where a path is a way to get from one node to another by means of following edges of the graph. From this, we can go into a connected graph, which is a graph where a path exists between any two nodes. Additionally, with paths there is a concept of distance between two nodes, which is defined as the fewest number of edges needed to get from one node to another. Next, trees are discussed. A graph is defined to be a tree if it is connected and without cycles. Trees are often rooted by a specific element and appropriately oriented around it. This is where the idea of child and parent nodes of a tree arise.

These definitions and explanations give us the tools needed to delve into one of the many algorithmic aspects of a graph, that is, traversing. Efficient traversal of a graph allows for a number of important implementations of graphs, which are, presumably, discussed in the next section.

I like graphs as I have studied them previously in math classes, and I even went to a talk on them today. As such, this section earns a whopping 8/10.

This sections open by discussing the need for an algorithm to determine s-t connectivity, which is the problem of determining whether or not there is a path connecting s and t. The book provides an alternate alias for this problem as the Maze-Solving Problem. The section goes on to discuss the high level descriptions of two algorithms meant to solve this problem, breadth first search and depth first search. The next section is meant to implement them. The book describes breadth first search as the simpler of the two algorithms for tackling the problem. It creates layer for each level of connections. By this, I mean you start at one node, which is the first layer, then you add every node connected to the first node by an edge to the second layer. The third layer is constructed from nodes connected by edges to nodes in the second layer, and so on and so forth. It is worth noting that not only does it determine if a path exists, but it also determines the shortest path. By drawing the appropriate edges across the layers, we can draw a breadth-first search tree for the starting node. Given that there can be more edges than needed to build the tree, extra edges not integral to the layer building are presented as dotted lines. These dotted lines can only be between nodes in the same layer or nodes in adjacent layers. If this were not the case, then the nodes should have been in adjacent layers.