1 Why Do We Need Graphs?
🌍 Real-World Problems
Network Everywhere!
From the neurons in your brain to the global internet, networks of connected elements are fundamental to how our world works. Graphs give us the tools to represent, analyze, and navigate these complex relationships.
2 Mental Model: Social Network Web
🕸️ Think of Graphs Like a Social Media Network
Like people in your social network - each has a unique identity
Like friendships or follows - they connect people together
Like mutual friendships - if A knows B, then B knows A
Like following on Twitter - A can follow B without B following back
🔄 Model Evolution: From Simple to Sophisticated
3 Graph Representations in Python
📊 Adjacency List
Like a contact list where each person has a list of their friends
# Adjacency List - Dictionary of Lists
graph = {
'Alice': ['Bob', 'Charlie'],
'Bob': ['Alice', 'David'],
'Charlie': ['Alice', 'David'],
'David': ['Bob', 'Charlie', 'Eve'],
'Eve': ['David']
}
# Check Alice's friends
print(graph['Alice']) # ['Bob', 'Charlie']📋 Adjacency Matrix
Like a friendship chart where 1 means "friends" and 0 means "not friends"
# Adjacency Matrix - 2D List
# People: Alice=0, Bob=1, Charlie=2, David=3, Eve=4
graph_matrix = [
[0, 1, 1, 0, 0], # Alice
[1, 0, 0, 1, 0], # Bob
[1, 0, 0, 1, 0], # Charlie
[0, 1, 1, 0, 1], # David
[0, 0, 0, 1, 0] # Eve
]
# Check if Alice (0) is friends with Bob (1)
print(graph_matrix[0][1]) # 1 (yes)4 Hands-on Practice: Build Your Network
🎨 Graph Visualization
📊 Adjacency List
🔍 Graph Analysis
5 Graph Traversal: Exploring the Network
🚶♂️ Breadth-First Search (BFS)
Like exploring your social network level by level - first your direct friends, then their friends, then their friends' friends
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
result = []
while queue:
node = queue.popleft()
if node not in visited:
visited.add(node)
result.append(node)
# Add neighbors to queue
for neighbor in graph[node]:
if neighbor not in visited:
queue.append(neighbor)
return result🏃♂️ Depth-First Search (DFS)
Like following one friendship chain as far as possible before backtracking
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
result = []
if start not in visited:
visited.add(start)
result.append(start)
for neighbor in graph[start]:
result.extend(dfs(graph, neighbor, visited))
return result🎮 Interactive Traversal
6 Critical Pitfall: Cycles and Infinite Loops
⚠️ The Infinite Loop Trap
Unlike trees, graphs can have cycles. Without proper tracking of visited nodes, your traversal can loop forever!
❌ Wrong: No Visited Tracking
# DANGER: This will loop forever in cyclic graphs!
def bad_dfs(graph, node):
result = [node]
for neighbor in graph[node]:
result.extend(bad_dfs(graph, neighbor)) # Infinite recursion!
return result
# With cycle A -> B -> A, this never stops!✅ Right: Track Visited Nodes
# SAFE: Always track visited nodes
def safe_dfs(graph, node, visited=None):
if visited is None:
visited = set()
if node in visited: # Stop if already visited
return []
visited.add(node)
result = [node]
for neighbor in graph[node]:
result.extend(safe_dfs(graph, neighbor, visited))
return result7 Knowledge Assessment: Graph Mastery
Question 1: Graph Representation
Which representation is more memory-efficient for a sparse graph (few edges)?
Question 2: Traversal Order
For the graph A-B-C where A connects to B and C, what's the BFS order starting from A?
Question 3: Cycle Detection
Why is tracking visited nodes crucial in graph traversal?