Graphs: Concepts and Operations

From structures to relationships

Now that you've finished Introduction to Data Structures, you know that choosing a structure changes what your code can do easily.

Graphs are our first major nonlinear structure in this course. Instead of storing items in a single line, graphs model relationships:

• Basketball players passing to each other
• Suspects, witnesses, and locations in a true-crime investigation board
• Cities connected by roads
• Friends connected in a social network

In this lesson, you'll learn the core vocabulary and implement basic graph operations in Python.

Nodes and edges

A graph is made of:

• Nodes / vertices: the things being represented
• Edges: the relationships between those things

Example: a basketball passing graph.

Ava ---- Ben
 |       /
 |      /
Mia --- Kai

Here, each player is a node. Each line is an edge, meaning those players have passed to each other.

Graphs are powerful because the same idea works for people, places, web pages, accounts, transactions, clues, dependencies, and more.

A social app lets users follow other users. If Jordan follows Riley, Riley does not automatically follow Jordan back.

What type of graph best represents this relationship?

A practical representation

One common way to store a graph is an adjacency list.

The idea: each node maps to the nodes directly connected to it.

For example:

Ava: Ben, Mia
Ben: Ava, Kai
Mia: Ava, Kai
Kai: Ben, Mia

In Python, a dictionary is a natural fit: keys are nodes, and values are lists or sets of neighboring nodes. We'll use dictionaries here without diving into hashing yet — that gets its own lesson later.

```python
# An undirected basketball passing graph using an adjacency list
passes = {
    "Ava": ["Ben", "Mia"],
    "Ben": ["Ava", "Kai"],
    "Mia": ["Ava", "Kai"],
    "Kai": ["Ben", "Mia"]
}

for player, neighbors in passes.items():
    print(f"{player} can pass directly to: {neighbors}")
```

In an adjacency list, each node maps to a collection of its direct _____.

Changing the graph

In the previous lesson, Operations Matter was a key theme. For graphs, the basic operations are:

• Add node: introduce a new item
• Add edge: connect two items
• Remove edge: disconnect two items
• Remove node: delete an item and its relationships

Below is a small reusable Graph class. It supports both directed and undirected graphs.

```python
class Graph:
    def __init__(self, directed=False):
        self.directed = directed
        self.adj = {}

    def add_node(self, node):
        if node not in self.adj:
            self.adj[node] = set()

    def add_edge(self, a, b):
        self.add_node(a)
        self.add_node(b)
        self.adj[a].add(b)
        if not self.directed:
            self.adj[b].add(a)

    def remove_edge(self, a, b):
        if a in self.adj:
            self.adj[a].discard(b)
        if not self.directed and b in self.adj:
            self.adj[b].discard(a)

    def remove_node(self, node):
        if node in self.adj:
            del self.adj[node]
        for neighbors in self.adj.values():
            neighbors.discard(node)

    def show(self):
        for node in sorted(self.adj):
            print(node, "->", sorted(self.adj[node]))

team = Graph(directed=False)
team.add_edge("Ava", "Ben")
team.add_edge("Ava", "Mia")
team.add_edge("Ben", "Kai")

print("Before removal:")
team.show()

team.remove_edge("Ava", "Ben")
team.remove_node("Kai")

print("\nAfter removal:")
team.show()
```

True or false: in an undirected graph, adding an edge between A and B should usually make B appear in A's neighbor list and A appear in B's neighbor list.

Thinking like a problem solver

Let:

• V = number of vertices/nodes
• E = number of edges/connections

With an adjacency list:

Operation Typical idea Add node Create an empty neighbor collection Add edge Add one or two neighbor entries Remove edge Delete neighbor entries Find neighbors Look up the node's stored list/set

The important habit is not memorizing a table yet. It's asking: what work does this representation make easy?

Adjacency lists are especially good when each node connects to only a small portion of the graph — common in real-world networks.

Visiting connected nodes

Once a graph exists, a common question is: what can I reach from here?

Two classic traversal strategies are:

• Breadth-first search, or BFS: explore nearby nodes first
• Depth-first search, or DFS: follow one path deeply before backing up

Think of a true-crime clue board: BFS checks all clues one step away from a suspect first; DFS follows one lead as far as it goes before trying another.

Here is an iterative version of both, so we can focus on graph behavior without using recursion yet.

```python
from collections import deque

graph = {
    "Suspect": ["Motel", "Witness"],
    "Motel": ["Suspect", "Receipt"],
    "Witness": ["Suspect", "Camera"],
    "Receipt": ["Motel"],
    "Camera": ["Witness"]
}

def bfs(start):
    visited = set([start])
    queue = deque([start])
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

    return order

def dfs(start):
    visited = set()
    stack = [start]
    order = []

    while stack:
        node = stack.pop()
        if node in visited:
            continue

        visited.add(node)
        order.append(node)

        # reversed keeps the example output predictable
        for neighbor in reversed(graph[node]):
            if neighbor not in visited:
                stack.append(neighbor)

    return order

print("BFS:", bfs("Suspect"))
print("DFS:", dfs("Suspect"))
```

You are building a route-finding graph for cities. Each node is a city.

What should an edge most likely represent?

What you can now do

You now have the foundation for working with graphs:

• A graph stores nodes and edges
• Directed edges have one-way meaning
• Undirected edges represent two-way relationships
• An adjacency list is a practical Python representation
• Core operations include adding/removing nodes and edges
• Traversals like BFS and DFS answer reachability questions

Graphs are one of the most flexible structures in computer science because they model relationships directly. Next, we'll study Recursion: Principles and Algorithms, which gives us another way to express step-by-step problem solving.