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.

A graph can either be represented with an adjacency matrix or an adjacency list. For more sparsely linked graphs, an adjacency list makes sense because we often need to look at all nodes connected to a particular node. While this is O(n) for both the matrix and the list, if a we assume a sparsely linked graph, the list requires less actual steps. Because both Breadth First Search and Depth First Search need to process a set of elements, we can maintain these elements in a linked list. We can use the linked list as a either a queue (first in first out) or a stack (last in first out). For Breadth First Search, we can have an array that tells if a node has already been seen or “discovered”. For Breadth First Search, we can use either queues or stacks to get O(m+n) (Where n is the number of nodes and m is the number of edges). For Depth First Search, we add all nodes adjacent to our current node to the stack, and then chose one path to follow. The stack works well because we only backtrack after all paths at the current node have been looked at. While these algorithms run on O(n+m) time, they do not necessarily find all nodes because they might not be part of the connected component, so finding connected components in O(n+m) as well.

A bipartite graph is one in which the set of nodes can be partitioned into two sets such that every edge has a node in one set and a node in the other. If a graph is bipartite, then it has no odd length cycles. To test for bipartiteness, we can perform a Breadth First Search and assign every odd numbered layer to one group and every even numbered layer to the other group. We can then test each edge to make sure that it has one node in the odd group and one node in the even group.