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.