As the title suggests, section 3.1 simply outlines the basic definitions that the book will use when discussing graphs.
When we want to keep track of asymmetrical relationships in a graph, we call this a directed graph. Directed graphs keep track of which edges lead to which nodes, but the nodes are not interchangeable. Thus, just because you can go from Node A to Node B, you can not necessarily go from Node B to Node A.
Undirected graphs, by contrast, imply that you can go both directions fro one node to the other. So, if you can move from Node A to Node B, you must always be able to move from Node B back to Node A.
The section then moves to defining connectivity. Connectivity is the property in which every node in a graph has a path to any other node. Thus, the graph cannot have any segment of the graph that is “floating” (i.e. not connected).
The concept of connectivity is important for the last section, which talks about tree structures. Trees are graphs that are fully connected, do not contain a cycle, and have n - 1 edges (n is the number of nodes in the graph). This serves to protect the structure of the tree. By making it be fully connected, we ensure that we can access every datum in the tree. By making sure there are no cycles, and that there are only n - 1 connections, we ensure each datum in the tree only has a parent-child relationship.
Thus, we can then arrange any graph that follows these three requirements into a tree shape.
This section covers two important strategies for reaching every node in a fully connected graph: breadth-first and depth-first search (BFS and DFS, respectively).
Breadth-first search explores every node directly connected to the starting node, then moves on to do the same for each of these newly explored nodes. The resulting tree shows layers that coincide with the distance from the starting node. For example, the first layer includes all nodes directly connected to the start node, the second layer includes all nodes twice removed from the start node, etc. This strategy is good for finding the shortest path from one node to another, as it always organizes itself around the distance from the start node.
Depth-first search does the opposite. BFS chooses a node to traverse to, then traverses to another node connected to it. It does this process recursively until it reaches a dead end, then backs up until it reaches an unexplored node. This results in a long, spindly tree. This tree is good for showing all of possible options, like solving a maze. It might not show the shortest path, but it will inevitably show the “correct” path.
This section describes how graphs can be best represented, then moves on to discuss the implementations of BFS and DFS.
Graphs can be represented two ways: they can be stored in either an adjacency matrix or an adjacency list. The adjacency matrix is built as an array of arrays, resulting in O(n2) storage space. The adjacency list, however, is built as an array of linked lists. These lists expand dynamically, resulting in O(m + n) space. Thus, the adjacency list is the more space efficient way of representing a graph. Adjacency matrices can access their data in constant time, however, while adjacency lists must search each list linearly. Thus, adjacency matrices allow for faster access of data.
Both the BFS and DFS algorithms put forward by this section run in O(m + n) time when stored in adjacency lists (pp. 91 and 93 for specific details).
This section describes bipartite graphs, and describes a strategy for determining whether a complex graph is bipartite.
A bipartite graph is any graph which does not contain an odd cycle. In simpler terms, consider each of the nodes to be colored either red or blue. In a bipartite graph, a blue node can only connect to a red node, and vice versa.
To determine whether or not a graph is bipartite, the first step involves running BFS on the graph. This will give us the layers of the graph. If any node on any level is connected to any node on that same level, the graph cannot be bipartite because the graph has to contain an odd cycle. This will always result in showing odd cycles, thus determining bipartiteness.
Up until this point in chapter 3, we have been working with undirected graphs. This section addresses how to deal with directed graphs.
In a directed graph, each edge has a direction. Since you can only follow the edge in the direction it points, this graph is considered directed. We represent directed graphs with two adjacency lists: one representing nodes that have edges pointing in, and one representing nodes that have edges pointing out.
The BFS and DFS strategies discussed for undirected graphs work almost identically for directed graphs. However, the graphs will appear slightly different depending on whether or not you can reach one node from another.