Graphs

AdvancedData Structures

Graphs model networks, dependencies, and relationships. Google interviews heavily feature graph problems: BFS for shortest paths, DFS for connectivity, topological sort for dependencies, and union-find for components.

AVG TIME

O(V + E)

SPACE

O(V + E)

BEST

O(1)

WORST

O(V + E)

Step-by-Step Walkthrough

step-by-step walkthrough

Breadth-First Search (BFS)

1 / 6

algorithm.py

1def bfs(graph, start):

2 visited = set()

3 queue = [start]

4 visited.add(start)

5 result = []

7 while queue:

8 node = queue.pop(0)

9 result.append(node)

11 for neighbor in graph[node]:

12 if neighbor not in visited:

13 visited.add(neighbor)

14 queue.append(neighbor)

16 return result

visualization

graph

currentvisitedin queue

edges: A-B, A-C, B-D, B-E, C-F

variable inspectorO(1) setup

visited={A}

queue=[A]

result=[]

The Graph

We have a graph: A connects to B and C. B connects to D and E. C connects to F. We start at A and want to visit all nodes. BFS explores ALL neighbors at the current level before going deeper.

speedmed

← →space

In Python

Concept to Code- 4 structures for this topic

declare

seen = {}  # or seen = dict()

common ops

seen[key] = val

O(1)

key in seen

O(1)

seen.get(key, default)

O(1)

del seen[key]

O(1)

seen.keys()

O(n)

seen.items()

O(n)

say in interview

"I'll use a hash map for O(1) lookups"

In Python, dict preserves insertion order (since 3.7). In interviews, don't rely on this unless asked.

Math You Need For This

Exploring a building. V = number of rooms. E = number of doorways. BFS explores all rooms on one floor before going to the next. DFS dives as deep as possible before backtracking.

Required concepts

Key math ideas

1 / 3

Graph theory - dots and lines

A graph is just dots (called nodes or vertices) connected by lines (called edges). That is it. A social network is a graph: people are nodes, friendships are edges. A city map is a graph: intersections are nodes, roads are edges.

Visual: Five circles on screen connected by lines between some pairs. Each circle is a node. Each line is an edge. If the lines have arrows, it is a directed graph (one-way streets). Without arrows it is undirected (two-way).

Think of it this way: Any network you can think of: power grid, airline routes, the internet, your friend group. All graphs.

For algorithms: Graph algorithms (BFS, DFS) work on any of these structures. Understanding what a graph IS makes the traversal algorithms click immediately.

Interactive 3D Visualization

Graph
BFS: O(V+E)DFS: O(V+E)Space: O(V+E)
Drag to orbit  -  Scroll to zoom

Python Implementation

example.py

Now try it yourself

2 challenges with test cases and AI feedback

Practice Now

Complexity Analysis

COMMON OPERATIONS

Array

Access:O(1)

Search:O(n)

Insert end:O(1)*

Insert mid:O(n)

Hash Map

Get/Set:O(1)*

Delete:O(1)*

Search value:O(n)

Iterate:O(n)

Linked List

Access:O(n)

Search:O(n)

Insert head:O(1)

Delete known:O(1)

Binary Search

Search:O(log n)

Insert:O(log n)

Balanced BST

Search:O(log n)

Insert:O(log n)

Delete:O(log n)

Heap

Peek min/max:O(1)

Push:O(log n)

Pop:O(log n)

Heapify:O(n)

Graph (BFS/DFS)

Traversal:O(V+E)

Dijkstra (heap):O((V+E) log V)

Merge / Quick Sort

Sort:O(n log n)

Space (merge):O(n)

Space (quick):O(log n)

* amortized average case

READY TO TEST YOURSELF?

Put Graphs into practice

The best way to lock in what you've learned is to write code. Solve real interview-style problems right now.

Next: Heaps / Priority Queues

Graphs

Next: Heaps / Priority Queues