Introduction to Graphs

You're building a social network. Users have friends. Alice is friends with Bob and Charlie. Bob is friends with Alice and David.

Arrays won't work—relationships go both ways. Trees won't work—no single root, and connections can form cycles.

You need graphs. Vertices (users) connected by edges (friendships).

What's a Graph?

Two components:

• Vertices: The things (users, cities, web pages)
• Edges: Connections between vertices (friendships, roads, links)

Take this friendship network:

  Alice --- Bob
    |        |
  Charlie - David

4 vertices, 4 edges. Alice connected to Bob and Charlie. Bob connected to David. Charlie connected to David.

That's it. Vertices and edges.

Directed vs Undirected

Undirected: Friendship is mutual. Alice friends with Bob means Bob friends with Alice.

Facebook works this way.

  A --- B
  |     |
  C --- D

Edge A-B goes both ways automatically.

Directed: Following isn't mutual. You follow someone who doesn't follow back.

Twitter works this way.

  A → B
  ↓   ↓
  C ← D

A follows B and C. B follows D. D follows C. That's all. C doesn't follow A back.

One-way arrows matter.

Weighted vs Unweighted

Unweighted: Edge exists or doesn't. No value attached.

  A --- B
  |     |
  C --- D

A connected to B. That's all we know.

Weighted: Edges have values. Distance, cost, time, whatever matters.

     5
  A --- B
  |3    |2
  C --- D
     4

A to B: 5 miles. A to C: 3 miles. Road network with distances.

Or flight network with prices. Or internet with latencies.

Common Patterns

Complete graph: Everyone connected to everyone.

  A --- B
  |\ /|
  | X |
  |/ \|
  C --- D

Every vertex has edge to every other. Rare in practice (expensive).

Cyclic: You can walk in a circle.

  A → B
  ↑   ↓
  D ← C

A → B → C → D → A. Back where you started. Cycle.

Acyclic: No circles possible. Trees are acyclic graphs.

Connected: Path exists between any two vertices.

Disconnected: Some vertices unreachable from others.

  A --- B    C --- D

A and B form one island. C and D form another. No bridge between them.

Storing Graphs in Memory

Three ways. Each has trade-offs.

Adjacency Matrix

2D array. Row i, column j = 1 if edge exists from i to j.

Take this graph:

  A --- B
  |     |
  C --- D

Map to indices: A=0, B=1, C=2, D=3.

Matrix:

    0  1  2  3
0 [[0, 1, 1, 0],  # A connected to B, C
1  [1, 0, 0, 1],  # B connected to A, D
2  [1, 0, 0, 1],  # C connected to A, D
3  [0, 1, 1, 0]]  # D connected to B, C

Check if A-B edge exists: matrix[0][1]. O(1).

For weighted graphs, store weight instead of 1:

graph = [[0, 5, 3, 0],
         [5, 0, 0, 2],
         [3, 0, 0, 4],
         [0, 2, 4, 0]]

Good: O(1) edge lookup.

Bad: O(V²) space. Even with few edges, allocate entire matrix.

For 1000 vertices, that's 1 million cells. If only 2000 edges? Wasteful.

Adjacency List

For each vertex, list its neighbors.

A: [B, C]
B: [A, D]
C: [A, D]
D: [B, C]

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D'],
    'D': ['B', 'C']
}

For weighted:

graph = {
    'A': [('B', 5), ('C', 3)],
    'B': [('A', 5), ('D', 2)],
    'C': [('A', 3), ('D', 4)],
    'D': [('B', 2), ('C', 4)]
}

Good: O(V + E) space. Only store what exists.

Bad: Checking if edge exists takes O(degree) time. Must scan neighbor list.

Most real graphs are sparse (few edges relative to possible). Adjacency list wins.

Edge List

Just list all edges.

edges = [
    ('A', 'B', 5),
    ('A', 'C', 3),
    ('B', 'D', 2),
    ('C', 'D', 4)
]

Good: Simple. Compact.

Bad: Finding neighbors of a vertex takes O(E) time. Must scan entire list.

Use for algorithms that iterate over edges (like Kruskal's minimum spanning tree).

Which to Choose?

Default to adjacency list. Switch to matrix if graph is dense or you check edges constantly.

Building a Graph

class Graph:
    def __init__(self):
        self.vertices = {}
    
    def add_edge(self, v1, v2, weight=None):
        # Add vertices if new
        if v1 not in self.vertices:
            self.vertices[v1] = []
        if v2 not in self.vertices:
            self.vertices[v2] = []
        
        # Add edge (undirected, so both ways)
        if weight:
            self.vertices[v1].append((v2, weight))
            self.vertices[v2].append((v1, weight))
        else:
            self.vertices[v1].append(v2)
            self.vertices[v2].append(v1)
    
    def neighbors(self, vertex):
        return self.vertices.get(vertex, [])

# Build network
g = Graph()
g.add_edge('Alice', 'Bob')
g.add_edge('Alice', 'Charlie')
g.add_edge('Bob', 'David')
g.add_edge('Charlie', 'David')

print(g.neighbors('Alice'))  # ['Bob', 'Charlie']

Clean. Simple. Works.

Degree

How many edges touch a vertex?

Undirected graph: Degree = number of neighbors.

Alice has degree 2 (connected to Bob and Charlie).

Directed graph: Split into in-degree (incoming) and out-degree (outgoing).

def degree(graph, vertex):
    return len(graph[vertex])

Why Graphs Matter

Trees force hierarchy. Arrays force order. Graphs impose neither.

Perfect for:

• Social networks (symmetric relationships)
• Road maps (cities and routes)
• Web pages (links)
• Dependencies (package managers, build systems)
• Game maps (locations and paths)

If your problem involves connections without strict hierarchy, think graphs.

The Pattern

Vertices connected by edges. Directed or undirected. Weighted or not. Store with adjacency list (usually).

That's graphs. Simple concept, powerful applications.