Graphs record relationships. Nodes are connected to one another by edges. In a directed graph, the order of nodes connected by edges is not interchangeable, but rather they are ordered pairs. If a graph does not specify direction, we assume that it is not directed. Examples of graphs in real life include computer networks, social networks, transportation networks, information networks like the world wide web, and dependency networks which capture the inter-dependencies between components of a system(ie: a food web in nature). In non directed graphs, a path is a sequence of connected nodes. Simple paths contain no repetition of vertices. Cycles are like paths but the first node must be the same as the last and there can be no repetitions. An undirected graph is connected if there is a path between each pair of nodes. It is strongly connected if there is a path between each pair of nodes in both “directions”. Distance between two nodes is the number of nodes in the shortest path between them. A graph is a tree if it is connected and does not contain a cycle. Review: one node in a tree(often the smallest, no parents) is the root, descendants of nodes are children and nodes with children are their parents. Trees imply the concept of hierarchy. Each tree has exactly n-1 edges where n is the number of nodes. This is because the root has no edges and each addition adds one node and only one additional edge. Overall, this section is a solid 8/10. Very nice read.

The s-t connectivity problem us finding if there is a path between nodes s and t in a graph. This challenge resembles solving a maze. One approach to finding a solution is breadth first search. In breadth first search, we start at a “root” node s. We then search all nodes connected to it (first layer). Then, we search all nodes connected to those nodes in the first layer(second layer). We repeat until there are no nodes remaining. The number of a layer Li corresponds to its path distance from s. Because they are in layers, searches correspond to a tree like structure called a breadth-first search tree. Only edges which connect to a new node are included in the tree(no two edges to the same node in the next layer). Nodes will not be searched if there is no path between them ans s. Thus, the set R of searched nodes is the connected component of the graph containing s. If t is in R, there is a path and vice versa. Another tactic for solving the problem is depth-first search. This is a recursive approach. For depth-first search, we start at s and then search one connected node a, then search a connected node of b, etc, until we reach a node without a connection to a non-searched node. Then, we backtrack until we find a node with unexplored edges. We must maintain a copy of the nodes which we can backtrack to. Depth first search ultimately produces the exact same connected component as breadth first search. However, its tree representation looks very different from breadth first as seen in class. This is called a depth-first search tree. If a pair of nodes (a, b) are directly connected in the breadth first search tree of a graph then one is the ancestor of the other in the corresponding depth first search tree. The connected components of two nodes in a graph are either identical or have no nodes in common. This property holds for all graphs. Thus, to find all connected components of a graph we could find one connected component R and then only find the connected components of nodes not in R. This section was interesting, complex and very well articulated by the book. I would give it a solid 8/10 for readability.

We use adjacency lists to represent graphs. We will treat nodes as n and edges as m, and compute run-time in terms of both n and m. We cannot say for sure if n or m is more significant, so we will treat them as equals. However, m⇐ n^2 always. For both breadth and depth search, we aim for O(n+m) time. An alternative representation is the adjacency matrix(constant access, O(n^2) space. Adjacency list: array of nodes with corresponding linked lists of connected edges for each node. Just O(n+m) space rather than O(n^2). Since the order of nodes is crucial, queues and stacks are ideal data structures to represent them. In BFS, nodes are organized using a queue while in DFS, nodes are organized using a stack(recursive). Finding the set of all connected components is still O(n+m) for both techniques. This section was harder to follow: 6.5/10.

Bipartite Graphs cannot have nodes in the same layer connect→ strategy: color each layer red or blue and if any edge has the same color on both ends the graph is not bipartite. These are “forward graphs”. If a graph is bipartite then it cannot contain an odd cycle. Algorithm: perform breadth first search to add colors. Then, after this step, scan through the resulting tree to see if condition is met. Unsurprisingly, the total running time of this algorithm is O(n+m).