Graphs and How to Represent Them

What a graph is

A graph is a way to describe things and the connections between them. It has two parts:

• Vertices (also called nodes): the things. A vertex could be a person, a city, a web page, or a task.
• Edges: the connections. An edge joins two vertices. An edge could mean “is friends with”, “has a road to”, “links to”, or “must happen before”.

That is the whole idea. Almost anything that involves relationships can be modeled as a graph: social networks, road maps, course prerequisites, the internet, dependencies between pieces of code.

We usually draw a vertex as a circle and an edge as a line between two circles.

graph LR
    A((A)) --- B((B))
    A --- C((C))
    B --- C
    C --- D((D))

This one has four vertices (A, B, C, D) and four edges (A-B, A-C, B-C, C-D).

Directed vs undirected

An edge can be one of two kinds.

• Undirected edge: the connection goes both ways. If A is friends with B, then B is friends with A. We draw it as a plain line.
• Directed edge: the connection has a direction, from one vertex to another. “A follows B” on social media does not mean B follows A. We draw it as an arrow.

A graph where every edge is directed is a directed graph (sometimes called a digraph). A graph where edges are undirected is an undirected graph.

graph TD
    subgraph Undirected
        U1((A)) --- U2((B))
        U2 --- U3((C))
        U1 --- U3
    end
    subgraph Directed
        D1((A)) --> D2((B))
        D2 --> D3((C))
        D3 --> D1
    end

On the left, A-B is a two-way connection. On the right, the arrows form a one-way loop: A to B, B to C, C back to A.

Weighted vs unweighted

Sometimes an edge carries a number, called its weight. The weight is a cost, distance, or capacity attached to the connection.

• Unweighted graph: edges have no numbers. Every edge is just “connected or not”.
• Weighted graph: each edge has a weight. For a road map, the weight might be the distance in kilometers. For a flight network, it might be the price.

graph LR
    A((A)) -->|5| B((B))
    A -->|2| C((C))
    C -->|1| B
    B -->|3| D((D))

Here the edge from A to B costs 5, but going A to C to B costs 2 + 1 = 3, which is cheaper. Weights are what let us ask questions like “what is the shortest route?”

Degree

The degree of a vertex is how many edges touch it.

In an undirected graph, degree is just the count of edges connected to that vertex. In the first undirected picture above, vertex A has degree 2 (edges to B and to C).

In a directed graph we split it into two:

• In-degree: how many arrows point into the vertex.
• Out-degree: how many arrows point out of the vertex.

In the directed loop above (A to B to C to A), every vertex has in-degree 1 and out-degree 1.

Paths and cycles

A path is a sequence of vertices where each one connects to the next by an edge. For example, in the weighted picture, A to C to B to D is a path. It “walks along” edges without lifting off.

A cycle is a path that starts and ends at the same vertex without reusing any edge along the way. The directed triangle A to B to C to A is a cycle. A graph with no cycles at all is called acyclic. A directed graph with no cycles is a DAG (directed acyclic graph), which is common for modeling dependencies, since a task cannot depend on itself through a loop.

Two ways to store a graph

Drawing a graph is fine for humans, but a program needs it as data. There are two standard representations. Understanding both, and when to use each, is the core skill of this lesson.

Adjacency list

An adjacency list stores, for each vertex, a list of the vertices it connects to (its neighbors). “Adjacent” just means “directly connected by an edge”.

In Python the natural form is a dictionary of lists. A dictionary (dict) maps a key to a value; here each key is a vertex and each value is the list of that vertex’s neighbors.

# Undirected graph: A-B, A-C, B-C, C-D
graph = {
    "A": ["B", "C"],
    "B": ["A", "C"],
    "C": ["A", "B", "D"],
    "D": ["C"],
}

print(graph["C"])        # -> ['A', 'B', 'D']  (C's neighbors)
print(len(graph["C"]))   # -> 3               (degree of C)

Note that in an undirected graph each edge appears twice: A lists B as a neighbor, and B lists A. That is because the connection goes both ways, so both endpoints must know about it.

For a directed graph you store an edge only in the source vertex’s list:

# Directed graph: A->B, A->C, C->B, B->D
graph = {
    "A": ["B", "C"],
    "B": ["D"],
    "C": ["B"],
    "D": [],           # D has no outgoing edges
}

print(graph["A"])   # -> ['B', 'C']   (where you can go from A)
print(graph["D"])   # -> []           (dead end)

To add a weight, replace each neighbor with a (neighbor, weight) pair:

# Weighted directed graph
graph = {
    "A": [("B", 5), ("C", 2)],
    "B": [("D", 3)],
    "C": [("B", 1)],
    "D": [],
}

for neighbor, weight in graph["A"]:
    print(neighbor, weight)   # -> B 5   then   C 2

Adjacency matrix

An adjacency matrix stores the graph as a grid (a table of rows and columns). Number the vertices 0, 1, 2, … Then cell in row i, column j answers one question: is there an edge from vertex i to vertex j? A 1 means yes, a 0 means no. (For a weighted graph you store the weight in the cell instead of 1.)

In Python a grid is a list of lists: the outer list holds rows, and each row is a list of cells.

# Same directed graph: A=0, B=1, C=2, D=3
# A  B  C  D
matrix = [
    [0, 1, 1, 0],   # from A: edges to B and C
    [0, 0, 0, 1],   # from B: edge to D
    [0, 1, 0, 0],   # from C: edge to B
    [0, 0, 0, 0],   # from D: none
]

# Is there an edge from A(0) to C(2)?
print(matrix[0][2])   # -> 1  (yes)
print(matrix[3][0])   # -> 0  (no edge D->A)

For an undirected graph the matrix is symmetric: an edge between i and j sets both matrix[i][j] and matrix[j][i] to 1, because the connection goes both ways.

It helps to see one small directed graph and then line up both representations against it.

graph LR
    A((A=0)) --> B((B=1))
    A --> C((C=2))
    C --> B
    B --> D((D=3))

As an adjacency list:

As an adjacency matrix (row = from, column = to):

Both describe exactly the same four edges. The list stores only what exists; the matrix reserves a cell for every possible pair, whether an edge exists or not.

Trade-offs and Big-O

To compare the two, we use Big-O notation, a way of describing how the cost grows as the graph gets bigger. Let:

• V = the number of vertices,
• E = the number of edges.

Big-O ignores constant factors and focuses on the shape of the growth. O(V) means “grows in proportion to the number of vertices”; O(1) means “constant, does not grow with the graph”.

Reading the table:

• Space. The list stores one entry per vertex plus one entry per edge, so O(V + E). The matrix always has V rows of V cells each, so O(V^2), even if there are almost no edges. Most real-world graphs are sparse (few edges relative to vertices), so the list usually wins on memory.
• Edge lookup. “Is there an edge from i to j?” With the matrix you read one cell, matrix[i][j], in O(1) constant time. With the list you must scan vertex i’s neighbor list until you find j or reach the end, which takes time proportional to i’s degree.
• Iterating neighbors. To visit everything reachable in one step from vertex i, the list hands you exactly that vertex’s neighbors, so the work matches the degree. The matrix forces you to scan the entire row of V cells and skip the zeros, so it is O(V) regardless of how few neighbors i has.

A rough rule: use an adjacency list for sparse graphs (the common case) and when you mostly walk along edges; use an adjacency matrix for small or dense graphs (many edges, close to V^2) or when you constantly ask “does this exact edge exist?”

Building a graph from an edge list

Often you are handed the edges and must build the structure. Here is a small, safe way to build an undirected adjacency list.

edges = [("A", "B"), ("A", "C"), ("B", "C"), ("C", "D")]

graph = {}
for u, v in edges:
    graph.setdefault(u, []).append(v)
    graph.setdefault(v, []).append(u)   # both directions: undirected

print(graph)
# -> {'A': ['B', 'C'], 'B': ['A', 'C'], 'C': ['A', 'B', 'D'], 'D': ['C']}

dict.setdefault(key, []) returns the list stored at key, first inserting an empty list if the key is not present yet. It saves you from checking “does this key exist?” by hand. For a directed graph, drop the second append line so each edge is recorded only once, from u to v.

Common pitfalls

• Forgetting the reverse edge in undirected graphs. If the connection is two-way, you must add it to both vertices’ lists. Add only one and your program will think you can walk A to B but not B to A.
• Mutable default arguments. Do not write def build(graph={}):. In Python a default value like {} is created once and shared across every call, so data leaks between calls. Use def build(graph=None): if graph is None: graph = {} instead.
• Assuming every vertex is a dictionary key. A vertex with no outgoing edges (like D above) still needs an entry, even if its list is empty. If you only add keys when you see an edge leaving them, graph["D"] will raise KeyError. Building from an edge list as shown, or initializing all vertices up front, avoids this.
• Matrix memory blowup. A matrix for 100,000 vertices needs 100,000 x 100,000 = 10 billion cells. For large sparse graphs the matrix is simply too big; reach for the list.
• Directed vs undirected confusion. Decide which one your problem is before you build. In a directed graph, matrix[i][j] and matrix[j][i] are independent; in an undirected graph they must stay equal.

Practice

1. Given the edge list [(0, 1), (0, 2), (1, 2), (2, 3)] for a directed graph, build the adjacency-list dictionary by hand, then write the 4x4 adjacency matrix. Check that your two answers describe the same edges.
2. Write a function out_degree(graph, vertex) that returns the number of outgoing edges of a vertex in an adjacency-list (dict of lists) directed graph. What is its time complexity in terms of that vertex’s degree?
3. Write a function to_matrix(graph, vertices) that converts an adjacency-list directed graph into an adjacency matrix, where vertices is the ordered list of vertex names giving each its row and column index. Return the matrix as a list of lists of 0s and 1s.