A graph allows us to encode pairwise relationships among a set of nodes. Each graph has both a set of nodes and a set of edges. Each edge connects two nodes. For a directed graph, it is important to note the direction of the edge in a ordered pair with the first node listed being the node that points to the second node listed. There are many examples of graphs. We can use graphs to model a transportation network, with nodes representing stops and edges representing direct routes between stops. Generally these are undirected graphs, but a directed graph is certainly conceivable. We can use graphs to model communication networks, with edges representing physical links between computer nodes. We can use graphs to model the World Wide Web with nodes representing web pages and edges representing hyperlinks. Since not all pages link back to every page that links to them, these graphs are directed. We can use graphs to model social networks, with nodes representing people and edges representing friendships or relationships. We can also use directed graphs to model dependency networks, like the prerequisites for taking a college course.

A path in an undirected graph is the sequence of nodes needed to get from one node to another. A “simple” path does not repeat any nodes, while a “cycle” ends where it began. A path in a directed graph is similar to a path in an undirected graph: we just need to make sure that we keep the directionality of the edges in mind. A “connected” undirected graph occurs when there is a path from every node to every other node. A “strongly connected” directed graph occurs when there is a path from every node to every other node, keeping in mind that the path must respect the directionality of the edges. The “distance” between any two nodes is the shortest path required to get from one node to the other. An “tree” is an undirected graph with no cycles. This allows us to represent a hierarchy.

The s-t connectivity problem asks if there is a path from node s to node t. Two algorithms for answering this problem are breadth-first search and depth-first search. Breadth first search puts node s in the first layer, and every node that has an edge with s goes in the second layer. Every new node that has an edge with a node in the second layer goes in the third layer, and this continues until no new nodes are found. The distance between nodes s and t is how many layers away they are. Breadth first search also gives us a tree rooted at s. Any nodes in the tree that have edges but are not in a parent-child relationship are at most one layer way. We can call all the nodes in these layers a connected component.

Depth-First search follows edges from s until it reaches a dead end. It then backtracks to a node with an unexplored edge and continues on that path until it reaches a dead end at which point it backtracks again. If we eventually get to t then we know there is a path from s to t.