Chapter 3 covers one of the most fundamental combinational structures, graphs.

3.1 - In this section, the books defines a graph as a collection of nodes (V) and a collection of edges (E) such that an edge joins two nodes. In order to construct an asymmetrical graph we construct a directed graph such that G' consists of a set of nodes V and set of directed edges E', where an edge (u,v) would be an edge that goes from node u to node v (but not necessarily the reverse). But by default, a graph is undirected unless desribes otherwise. Along with the definition, the section provides a list of real life examples of graphs. The next part of the section defines a path, a cycle, and connectivity, such that a path is a sequence of nodes such that each node has a edge to connect it with the following node. A cycle is a path that “cycles back” to where it began, and finally, a graph is connected if each pair of nodes u and v has a path from u to v. The last part of the section defines a “tree” as a particular kind of graph that is connected but does not cycle.

3.2 - This section of the chapter asks how a person would know if a graph is connected, and how efficiently can that answer be found. The section answers this question with two possible algorithms: Breadth-First Search (BFS) and Depth-First Seach (DFS). BFS simply starts with the root and then floods the graph one layer at a time, where subsequent layer is of 1 length from the previous. More specifically, BFS starts with the root and then searches for its children. If the root has children, then the algorithm records them. BFS only moves from one layer to the next once each node of the layer has been checked for its children. This algorithm is done recursively until it reaches its end. On the other hand, DFS is similar to BFS. However DFS searches by starting with the root and try to find the first edge leading out of it (v), then it follows the first edge leading out of v and continute until it reached a “dead-end”. After the algorithm backtracks until it finds a node witha n unexplored neighbor, and resumes from the recrusion from there. The last part of the section proves that for any two nodes s and t in a graph, their connected components are either identical or disjoint for both BFS and DFS.

3.3 - This section describes two representations of graphs: an adjacency matrix and an adjacency list. An Adjacency matrix finds all its nodes and edges with constant time but uses up O(n-squared) space. Yet an adjacency list can be represented either by a queue of a stack. Queues and stacks are both doubly linked lists but a queue adds elements to the back where as a stack adds elements to the front. If this is true, then BFS algorithms can be implemented using queues. Therefore when we are scanning the edges leaving u (in an adj-list) and come to an edge (U,V), we need to know whether or not node v has been previosuly discovered by teh search. To make this simple the structure maintains an array “discovered” of length n and set discovered[v]=true when the search first encounters v. Along with the implementation the book describes the efficiency of the algorithm as O(m+n) such that m = number of edges and = number of nodes. Lastly, the section shows that one can implement a DFS by using a stack. It is implemented similarily to BFS but instead of using “discovered”, it uses “explored[v]=true” to show that a v's edges have been scanned. Again, this algorithm also runs in O(m+n) time.

3.4 - In this section the book covers a bipartite graph, what it means, and how to prove if a graph is bipartite. By definiton, a bipartite graph has teh node set V that can be partitioned into sets X and Y in such a way that every edge has one end in X and the other end in Y (X colored red and Y colored blue). Also, the book proves that bipartite graphs can never exist is graph contains an odd cycle becasue eventually a the final node of the cycle would end in red meaning its edge points to a red node. The easiest way to solve if a graph is bipartite is using BFS such that each layer of the graph would be either red or blue.

3.5 - This last section looks at directed graphs, and compares them to undirected graphs. A directed graph cna be represented also by queues and stacks, similarly to undirected graphs, but instead of each node having a list of neighbors, each node has two lists associated with it: one of teh nodes to which it has edges, and the second of nodes from which it has edges. These algorithms also run in O(m+n) time. Next, the chapter discusses the idea of “strong connectivity” and being mutually reachable. It proves that if nodes u and v are mutually reachable, and v and w are mutually reachable then u and w are mutually reachable. Lastly, the book shows that one can find if a directed graph is strongly connected if the graph G's nodes are all mutually reachable and the graphs reverse, Grev's nodes are all mutually reachable. And like an undirected graph, for any two nodes of a directed graph, their strong components are either identical or disjoint.