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:

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:

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.

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).

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

### See also:

- Breadth-First Search (BFS) and Breadth-First Traversal
- Depth-First Search (DFS) and Depth-First Traversal
- Binary Trees
- Linked Lists

## 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.

You're in! Head over to your email inbox right now to read day one!