Graph Data Structure

A graph is a data structure that stores data in nodes that are connected to each other.

Graphs are useful to represent relationships between entities.

Here is a simple example of a graph:

For example, a social network like LinkedIn can be modeled after a graph, where users are connected to eachother. Some users are first degree connections, second degree, or not connected at all.

Let's use this graph to define some common graph terminology.

Each node, or vertex, in the graph contains a number. In no particular order, the graph above contains the following vertices:

V = [6, 4, 2, 9, 7]

The lines that connect each node are called edges. The following is a list of edges in the same graph:

E = [ (6, 4), (6, 2), (6, 9), (2, 7) ]

Sometimes, graph edges may have weights, which indicates some sort of cost to from from one node to another.

Vertices are adjacent to eachother if they are connected via an edge.

We can say that the node with 6 is adjacent to the node with 4.

Finally, a path exists between two nodes, or vertices, if there are a set of edges that connect them.

For example, there exists a path from node 4 to node 9: [4, 6, 9]

There are a few ways to represent a graph in code.

Given a graph with V vertices, we can represent the graph with a V x V matrix.

Each item in the matrix at (i, j) represents if there is an edge that exists between node i and node j.

If the edge exists, the value is 1. While the value 0 indicates that there is no edge.

Here's the adjacency matrix for our example graph.

As you can tell, an adjacency matrix isn't very storage efficient, especially when the number of edges is small, or sparse. For example, the edge between 4 and 6 is stored in 2 places in our matrix: (0, 2) and (2, 0).

An adjacency list is a collection of unordered lists, where each list tracks a single node's neighbors.

Using the same graph as an example, here is what the adjacency list looks like:

In an adjacency list, each list can be either an array or linked list, where the head is the node that the list represents, and the connected nodes are its edges (or neighbors).

Now if the graph is sparse, we save space as we only store edges that exist.

In Python, that adjacency list A for the vertices V looks something like this:

V = [6, 4, 2, 9, 7]
A = [
        [4, 2, 9],
        [6, 2],
        [7],
        [6],
        [2]
]