Basics

Let's now turn our attention to yet another fundamental data structure: graphs. Just like other data structures, such as arrays, linked lists, and trees, graphs are a building block on which we can build other abstractions to solve complex problems.

We have discussed graphs to some degree in previous courses, so let's begin with a review of graphs and the associated terminology. To begin with, here's an example of a graph:

Each graph, including the one above, is defined in terms of a set of vertices $$V$$ (also known as *nodes) and a set of edges $$E$$. Each edge connects a pair of vertices.

Graphs therefore give us the ability to represent entities and the relationships between them. For example, social networks are most naturally represented as graphs.

Here's another example: a graph that shows the connectedness of some cities:

In this case, the vertices represent cities, and the edges represent the lengths of the roads between these cities. This is actually an example of a weighted graph, since there is a cost associated with each edge. Eventually, we'll be able to represent problems as graphs, and then ask questions like: what's the shortest route from Abuja to Port Harcourt?

Watch the following videos to learn about the basics of graphs:

Terminology

As you can see from the videos, there is a lot of terminology associated with graphs. Let's revisit some of the more important concepts below with examples:

Adjacent

Two vertices are adjacent if they are connected by a single edge.

For example, in the graph below, nodes $$d$$ and $$f$$ are adjacent, but $$f$$ and $$j$$ are not adjacent.

Neighbors

The collection of vertices that are adjacent to a vertex $$v$$ are known as the neighbors of $$v$$. For example, the neighbors of $$d$$ are $$c$$, $$f$$, and $$e$$.

Path

A path in a graph is a sequence of edges that connects two vertices. For example, here's a graph with a highlighted path:

Connected

A graph is connected if there is a path between any two pairs of vertices. The graph above is connected, but the following six vertices (all part of the same graph) are not connected:

Sometimes, we call the different parts of an unconnected graph islands, as in, the above graph has two islands of vertices.

Note: Depending on context, you might consider the above image to consist of two connected graphs or one unconnected graph.

Complete

A graph is complete if there is an edge between every pair of vertices. Here's an example:

Directed

A directed graph has a direction associated with each edge, which is depicted using an arrow:

Edges in a directed graph are often represented as ordered pairs of the form (start vertex, end vertex). For example, $$(a, b)$$ is an edge in the graph above, but $$(b, a)$$ is not.

Graphs which have no direction on edges are known as undirected graphs.

Cycles

A cycle is a path that leaves a given vertex using one edge, and then later returns to that same vertex using a different edge. For example:

Now that we know a bit about graphs and the terminology used to describe them, we can turn our attention to ways to represent graphs in programs.