Welcome to Programming and Data Structures

A graph is the name we give to a collection of elements called vertices (or sometimes nodes) that are connected by links called edges.

Graphs are a very general structure that can be used to model a wide variety of problems. For example, we can use a graph to represent a road map, where the vertices are cities and the edges are roads connecting those cities. We can also use a graph to represent a social network, where the vertices are people and the edges represent friendships. Or we can use a graph to represent the courses we need to take in order to complete a major in computer science, where the vertices are courses and the edges represent prerequisite relationships.

There are many complications that can be added to the basic idea of nodes connected by edges. In a directed graph, edges only link in one direction. This is the case in the prerequisite chart above. The link from CS160 to CS161 is drawn with an arrow pointing at CS161 to show that CS160 is a prerequisite to CS161. You can go from CS161 to CS160, but not vice verse. If we wanted to show links going in both directions in a directed graph, we would draw arrows pointing both ways or separate lines traveling in each direction.

In an undirected graph, each edge links in both directions. This is the case in the social network graph above. The link between Erin and Charlie is not drawn with an arrow because it represents a mutual friendship.

In a weighted graph, edges have values associated with them. For example, in the driving distances graph above, the edges have weights that represent the distance between cities. These values typically represent something like the cost, length, or capacity of the connection. In an unweighted graph, every edge has the same value (typically thought of as 1).

Some graphs may allow for multiple parallel edges that connect the same two nodes (in the same direction in a directed graph). If all we care about is “can you reach A from B?”, and existing edges can’t be removed, then we likely don’t care about parallel edges. However, in modeling other situations, like modeling traffic, knowing there are multiple routes from A to B might be important.

Typically, we name vertices, either using numbers or strings. We might refer to the vertices in the friendship graph as {Anna, Ben, Charlie, Diego, Erin, Fred}, or might shorten those to {A, B, C, D, E, F} or call them {v1, v2, v3, v4, v5, v6}.

Edges are referred to by the vertices they connect. So the edge (Anna, Ben) connects the vertices Anna and Ben. In a directed graph, the edge pair is ordered, with the first vertex being the source and the second vertex being the destination. So in the prerequisite graph, the edge (CS160, CS161) would describe the edge that pointing from CS160 to CS161. If we needed to refer to the edge in the opposite direction, we would write (CS161, CS160). To specify a weight, we would write something like (Portland, Salem, 47) to indicate the edge from Portland to Salem with a weight of 47 miles.

Many graph algorithms focus on computing paths through a graph. A path is an ordered sequence of vertices where each adjacent pair of vertices is connected by an edge. For example, in the prerequisite graph, (CS160, CS161, CS162) is a path from CS160 to CS162. In the social network graph, (Anna, Diego, Erin) is a path from Anna to Erin.

Another path from Anna to Erin is (Anna, Ben, Diego, Anna, Diego, Erin). This second path is a bit silly because it contains a loop—a path that starts and ends at the same vertex: (Anna, Ben, Diego, Anna). If we are trying to connect Anna to Erin, there is no need to A simple path is one that does not contain any loops (like (Anna, Ben, Diego, Erin)).

Graph theory is a rich field of study that overlaps both mathematics and computer science. We will not be diving deeply into the mathematics of graphs, or the notation used to describe them. Instead, we will focus on some fundamental techniques for writing code to represent and manipulate graphs and a few important algorithms that operate on graphs.