Objectives

By the end of this chapter you should be able to:

• Define a graph data structure and compare and contrast different kinds of graphs
• Understand applications of graphs in computer science and programming
• Implement three representations of graphs using adjacency lists and adjacency matrices

Introduction

Before we dive deep into how a graph works, let's see what one looks like and then compare and contrast it to the previous data structures we have seen. Here's a graph:

You might be thinking that this looks very similar to a binary search tree! In fact, trees are a certain type of graph. The concept of a graph, however, is more general: all trees are graphs, but not all graphs are trees.

Graphs consist of nodes (which are also called vertices) and can be displayed in many different ways. The connections between vertices are called edges. Here's another example of a graph:

So what is different about this graph than the one above? We can see in this graph that the edges have a direction! Put another way, there are arrows pointing to different vertices. We can even go from one vertex (B) to another (C) to (E) to (D) and back to (B) in a cycle! We will soon learn the term for this type of graph; for now, the important thing to understand is that there are many different kinds. Before we define all the terms, let's look at one more kind of graph.

What differences do you see here? In this graph the edges have numbers associated with them! When we create graphs, we can place weights between nodes to represent some sort of cost to travel from one node to another.

Essential Vocabulary

Now that we have seen a few graphs, let's define some common terms. We've used some of these already, but others may be new to you:

Vertex - Similar to nodes, each vertex represents a piece of data in the graph .
Edge - Vertices/nodes are connected by edges.
Weighted - Weighted graphs have values placed on each edge, which represents the cost to travel from that node to another.
Unweighted - In an unweighted graph, there is no value placed on traversing from one node to another.
Directed - In a directed graph, edges can have a direction which restricts motion along them. If an edge points from node A to node B, for instance, then it's possible to move from A to B, but not from B to A. Edges in a directed graph can be either unidirectional (one-way) or bidirectional (two-way).
Undirected - in an undirected graph, every edge is bidirectional; in other words, as long as an edge exists, there's no restriction on travel between the two nodes.
Acyclic - An acyclic graph is where you can never traverse from a single node back to itself. Here's an example of an acyclic graph:

Cyclic - A cyclic graph is a graph which is not acyclic.

Before we continue, take a look at the graphs above! Now that you know more of the terminology, which ones are weighted or unweighted? Which ones are directed or undirected? Which ones are cyclic or acyclic?

Applications of Graphs

Hopefully you have started to see how powerful graphs can be, but let's list some real world use cases for graphs.

Networking - We can model the entire Internet as a series of nodes connected in a graph.
Social Networking - Imagine how you could model your social network of friends on Facebook or LinkedIn. We could use an undirected graph to display connections between friends and build sophisticated algorithms for expanding a social network. The graph is undirected because friendship is bidirectional: if I'm friends with you, then you're friends with me. Not all social networking is bidirectional, though: for example, you can follow someone on Twitter without them following you back. How does this change the structure of a graph model of users on Twitter, as compared to Facebook?
Navigation - How could we model something like Google Maps? We can think of navigation as a massive directed weighted graph with distances between each location and endless paths for getting from one point to another. We will see in a later section how we can find the shortest path between two locations!
Games/Mazes - Very commonly, games will implement forms of graph traversal specifically with mazes. We could model a maze as a series of nodes with an optimal path for someone to complete.

Representing Graphs

What makes graphs tricky to implement is that there are multiple ways of representing the data structure programmatically. Unlike our representations of linked lists and binary search trees, which are collections of nested objects, we have a few different ways of representing graphs. Let's examine three approaches.

Adjacency List

An adjacency list is a collection of lists which contain the neighbors of a vertex (i.e. the vertices where are connected to the given vertex by an edge). There are many different implementations of adjacency lists, but we will be using an object to model this with the keys being the verticies and the values being an array of edges. Given the following graph, here is what our adjacency list would look like:

var adjacencyList = {
  1: [2, 5],
  2: [1, 3, 5],
  3: [2, 4, 5],
  4: [3, 5, 6],
  5: [1, 2, 4],
  6: [4]
};

This object indicates that vertex 1 is connected to vertices 2 and 5, vertex 2 is connected to vertices 1, 3, and 5, and so on.

You can read more about adjacency lists here.

Adjacency Matrix

An adjacency matrix is a two-dimensional matrix whose values contain information on the adjacency of pairs of vertices. More specifically, the value of the matrix in the *i*th row and *j*th column indicates whether or not vertex i and vertex j are adjacent.

Here's an example of an adjacency matrix for our undirected graph from before:

You can read more about adjacency matrices here.

Additional Representations

Incedence Matrix - A two-dimensional Boolean matrix, in which the rows represent the vertices and columns represent the edges. The entries indicate whether the vertex at a row is incident to the edge at a column. Here is what that might look like:

In this example, the sign of the value in the matrix corresponds to the direction of the edge. For instance, edges 1 and 4 are leaving vertex a, so the values for (a, 1) and (a, 4) in the matrix are both +1. Similarly, edge 3 is entering vertex a, so the value for (a, 3) is -1. Finally, edge 2 doesn't touch vertex a, so the value for (a, 2) is 0.

Edge List - One simple way to represent a graph is just a list, or array representing the edges of the graph. To represent an edge, we just have an array of two vertex numbers, or an array of objects containing the vertex numbers of the vertices that the edges are incident on. If edges have weights, add either a third element to the array or more information to the object, giving the edge's weight.

Here's how we could create an edge list for our undirected graph from before:

var edgeList = [[4, 6], [4, 3], [4, 5], [3, 2], [5, 2], [5, 1], [2, 1]];

Performance Differences

Most of the time, adjacency lists will be used unless you are working with a dense graph (a graph where the number of edges is close to the number of verticied squared) or if you need to quickly look up if there is an edge connecting two nodes. Here is a performance comparison of adjacency lists and adjacency matricies. These will be represented in Big O notation with |V| being the number of verticies and |E| being the number of edges.

You can compare these approaches here and read more here.

Modeling our Graph in JavaScript

For our implementation of a graph, we will be using an adjacency list.

function Graph() {
  this.adjacencyList = {};
}

When we add a vertex, we just add a new key in the object with an empty array as its value. When we add an edge, we push the vertex into the corresponding array for the vertex it is connected to.

Additional Resources

Khan Academy

Exercises

Complete Part I of the Graphs Exercises.