Chapter 3

A graph is a collection of V nodes and E edges where an edge e is represented as a two-element subset {u, v}. Directed graphs represent an edge e in ordered pairs (u, v), which are not interchangeable. An undirected graph is essentially a default graph. Examples of graphs include transportation, communication, information(e.g. world wide web), social, and dependency networks. An important operation in graphs is traversing a sequence of nodes connected by edges. Traversal requires that a path, a sequence of of connected nodes, exist. An undirected graph is corrected if there exists a path between every pair of nodes. Interestingly, trees are undirected graphs that do not contain a cycle (the sequence of nodes does not cycle back to where it begins). Overall the section was a basic overview of graphs, and it's readability is an 8/10.

Chapter begins with introduction to the problem of determining connectivity between two nodes, s and t. One algorithm for determining connectivity is Breadth-First Search (BFS), which explores outwards from s layer by layer. BFS outputs a tree. Another natural way of determining connectivity between s and t is Depth-First Search (DFS). Unlike BFS, DFS explores outward from s following a path of connected edges until it reaches a dead end. It then backtracks to a node with an unexplored neighbor and tries another route. DFS also outputs a tree, but of a very different shape. Both algorithms are O(n+m) in run time. Another important subject in this section is a Connected Component. The connected component of a node s is the set of nodes reachable from s. For any two nodes s and t in a graph, their connected components are either identical and disjoint. Overall, the readability of this section is 8/10.

There are two ways to represent a graph: an adjacency matrix and an adjacency list. When discussing nodes and edges, n represents the number of nodes and m the number of edges. The goal for graph search algorithms is O(n+m), which is technically referred to as linear time.