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.