Graphs

A graph is an abstract data structure with nodes (or vertices) that are connected by edges.

.

They're useful in cases where you have things that connect to other things. Nodes and edges could, for example, respectively represent cities and highways, routers and ethernet cables, or Facebook users and their friendships.

Two nodes connected by an edge (like A and B) are adjacent or neighbors.

.

The degree of a node is the number of edges connected to the node.

.

Graphs can be directed or undirected. In directed graphs, edges point from the node at one end to the node at the other end. In undirected graphs, the edges simply connect the nodes at each end.

.

In a directed graph, nodes have an indegree and an outdegree.

.

If a graph is weighted, each edge has a "weight." The weight could, for example, represent the distance between two locations, or the cost or time it takes to travel between the locations.

.

A graph is cyclic if it has a cycle—an unbroken series of nodes with no repeating nodes or edges that connects back to itself. Graphs without cycles are acyclic.

.

A loop is an edge that connects a node to itself.

.

Graphs are commonly represented in several ways. Let's take this graph as an example:

.

Edge list

A list of all the edges in the graph:

graph = [[0, 3], [1, 2], [1, 3], [2, 3]]

Since node 1 has edges to nodes 2 and 3, [1, 2] and [1, 3] are in the edge list.

Sometimes it's helpful to pair our edge list with a list of all the nodes. For example, what if a node doesn't have any edges connected to it? It wouldn't show up in our edge list at all!

Adjacency list

A list where the index represents the node and the value at that index is a list of the node's neighbors:

graph = [ [3], [2, 3], [1, 3], [0, 1, 2], ]

Since node 1 has edges to nodes 2 and 3, graph[1] has the adjacency list [2, 3].

We could also use a dictionary where the keys represent the node and the values are the lists of neighbors.

graph = { 0: [3], 1: [2, 3], 2: [1, 3], 3: [0, 1, 2], }

This would be useful if the nodes were represented by strings, objects, or integers that aren't sequential from a low number.

Adjacency matrix

A matrix of 0s and 1s indicating whether node x connects to node y (0 means no, 1 means yes).

graph = [ [0, 0, 0, 1], [0, 0, 1, 1], [0, 1, 0, 1], [1, 1, 1, 0], ]

Since node 1 has edges to nodes 2 and 3, graph[1][2] and graph[1][3] have value 1.

See also:

Pass Your Interviews with My FREE 7-Day Crash Course

I'll teach you the right way of thinking for breaking down tricky algorithmic coding interview questions you've never seen before.

No prior computer science training necessary—I'll get you up to speed quickly, skipping all the overly academic stuff.

No spam. One-click unsubscribe if you hate it.

Psst. Pass it on.

. . .