- Apply graphs to social networks: mutual friends, recommendations with set intersection
- Implement topological sort for dependency resolution in O(V+E)
- Detect cycles with DFS for deadlock detection in wait graphs
Graph Applications
Graphs aren't just theory. They solve real problems everywhere.
Social Networks
Facebook, LinkedIn, Twitter—all graphs. Users are vertices. Friendships/follows are edges.
Find mutual friends:
def mutual_friends(graph, user1, user2):
friends1 = set(graph[user1])
friends2 = set(graph[user2])
return friends1 & friends2 # Intersection
graph = {
'Alice': ['Bob', 'Charlie', 'David'],
'Bob': ['Alice', 'Charlie'],
'Charlie': ['Alice', 'Bob', 'Eve'],
'David': ['Alice'],
'Eve': ['Charlie']
}
print(mutual_friends(graph, 'Alice', 'Bob')) # {'Charlie'}
Friend recommendations (friends of friends):
def recommend_friends(graph, user):
friends = set(graph[user])
recommendations = set()
for friend in friends:
for friend_of_friend in graph[friend]:
if friend_of_friend != user and friend_of_friend not in friends:
recommendations.add(friend_of_friend)
return recommendations
print(recommend_friends(graph, 'Alice')) # {'Eve'}
Eve is friend of Charlie (Alice's friend), but not Alice's direct friend. Recommended.
Web Crawling
Web pages are vertices. Links are directed edges.
from collections import deque
def web_crawler(start_url, max_pages):
visited = set()
queue = deque([start_url])
crawled = []
while queue and len(crawled) < max_pages:
url = queue.popleft()
if url in visited:
continue
visited.add(url)
crawled.append(url)
# Get links from page (simplified)
links = get_links(url)
for link in links:
if link not in visited:
queue.append(link)
return crawled
BFS ensures breadth-first exploration. Stays close to start before going deep.
Dependency Resolution
Build systems, package managers. A depends on B, B depends on C. What order to build?
Topological sort.
def topological_sort(graph):
in_degree = {v: 0 for v in graph}
# Calculate in-degrees
for vertex in graph:
for neighbor in graph[vertex]:
in_degree[neighbor] += 1
# Queue of vertices with no dependencies
queue = deque([v for v in graph if in_degree[v] == 0])
result = []
while queue:
vertex = queue.popleft()
result.append(vertex)
# Remove this vertex, decrease in-degrees
for neighbor in graph[vertex]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
# If result doesn't contain all vertices, cycle exists
if len(result) != len(graph):
return None # Cycle detected
return result
# Build system
dependencies = {
'main.o': ['utils.o', 'data.o'],
'utils.o': ['types.o'],
'data.o': ['types.o'],
'types.o': []
}
print(topological_sort(dependencies))
# ['types.o', 'utils.o', 'data.o', 'main.o'] or ['types.o', 'data.o', 'utils.o', 'main.o']
Build types.o first (no dependencies), then utils.o and data.o, finally main.o.
Finding Paths
GPS, routing, game AI. Find path from A to B.
def find_path_dfs(graph, start, goal, path=None):
if path is None:
path = []
path = path + [start]
if start == goal:
return path
for neighbor in graph[start]:
if neighbor not in path: # Avoid cycles
new_path = find_path_dfs(graph, neighbor, goal, path)
if new_path:
return new_path
return None
cities = {
'NYC': ['Boston', 'Philly'],
'Boston': ['NYC'],
'Philly': ['NYC', 'DC'],
'DC': ['Philly']
}
print(find_path_dfs(cities, 'Boston', 'DC'))
# ['Boston', 'NYC', 'Philly', 'DC']
All paths:
def find_all_paths(graph, start, goal, path=None, paths=None):
if path is None:
path = []
if paths is None:
paths = []
path = path + [start]
if start == goal:
paths.append(path)
return paths
for neighbor in graph[start]:
if neighbor not in path:
find_all_paths(graph, neighbor, goal, path, paths)
return paths
print(find_all_paths(cities, 'Boston', 'DC'))
# [['Boston', 'NYC', 'Philly', 'DC']]
Detecting Deadlocks
Processes waiting for resources. Cycle in wait graph = deadlock.
def has_deadlock(wait_graph):
visited = set()
rec_stack = set()
def dfs(process):
visited.add(process)
rec_stack.add(process)
for waiting_for in wait_graph.get(process, []):
if waiting_for not in visited:
if dfs(waiting_for):
return True
elif waiting_for in rec_stack:
return True # Cycle = deadlock
rec_stack.remove(process)
return False
for process in wait_graph:
if process not in visited:
if dfs(process):
return True
return False
# Process A waits for B, B waits for C, C waits for A
deadlock_graph = {
'A': ['B'],
'B': ['C'],
'C': ['A']
}
print(has_deadlock(deadlock_graph)) # True
Finding Strongly Connected Components
Directed graph. Strongly connected component (SCC): every vertex reachable from every other.
def kosaraju_scc(graph):
# Step 1: Fill order (finish times)
visited = set()
stack = []
def dfs1(v):
visited.add(v)
for neighbor in graph.get(v, []):
if neighbor not in visited:
dfs1(neighbor)
stack.append(v)
for vertex in graph:
if vertex not in visited:
dfs1(vertex)
# Step 2: Transpose graph
transposed = {v: [] for v in graph}
for v in graph:
for neighbor in graph.get(v, []):
transposed[neighbor].append(v)
# Step 3: DFS on transposed in reverse finish order
visited.clear()
sccs = []
def dfs2(v, component):
visited.add(v)
component.append(v)
for neighbor in transposed.get(v, []):
if neighbor not in visited:
dfs2(neighbor, component)
while stack:
vertex = stack.pop()
if vertex not in visited:
component = []
dfs2(vertex, component)
sccs.append(component)
return sccs
graph = {
'A': ['B'],
'B': ['C'],
'C': ['A'],
'D': ['B', 'E'],
'E': ['F'],
'F': ['D']
}
print(kosaraju_scc(graph))
# [['D', 'F', 'E'], ['A', 'C', 'B']]
Two SCCs: {A, B, C} and {D, E, F}.
Course Prerequisites
Courses have prerequisites. Can you complete all courses? Is ordering possible?
def can_finish_courses(num_courses, prerequisites):
# Build graph
graph = {i: [] for i in range(num_courses)}
in_degree = {i: 0 for i in range(num_courses)}
for course, prereq in prerequisites:
graph[prereq].append(course)
in_degree[course] += 1
# Topological sort
queue = deque([c for c in range(num_courses) if in_degree[c] == 0])
count = 0
while queue:
course = queue.popleft()
count += 1
for next_course in graph[course]:
in_degree[next_course] -= 1
if in_degree[next_course] == 0:
queue.append(next_course)
return count == num_courses
# Course 1 requires 0, Course 2 requires 1, Course 3 requires 1 and 2
prereqs = [[1, 0], [2, 1], [3, 1], [3, 2]]
print(can_finish_courses(4, prereqs)) # True
# Circular: 1 requires 0, 0 requires 1
circular = [[1, 0], [0, 1]]
print(can_finish_courses(2, circular)) # False (cycle)
Clone a Graph
Deep copy a graph.
class Node:
def __init__(self, val, neighbors=None):
self.val = val
self.neighbors = neighbors if neighbors else []
def clone_graph(node):
if not node:
return None
visited = {}
def dfs(n):
if n in visited:
return visited[n]
clone = Node(n.val)
visited[n] = clone
for neighbor in n.neighbors:
clone.neighbors.append(dfs(neighbor))
return clone
return dfs(node)
DFS creates copy while traversing. Hash map prevents infinite loops.
When to Use Graphs
Relationships matter: Social networks, dependencies, connections.
Path finding: Navigation, routing, reachability.
Network flow: Traffic, pipelines, internet routing.
Ordering: Topological sort for dependencies.
Clustering: Connected components, communities.
When NOT to Use
Hierarchical with single parent: Use tree instead.
Sequential access: Use array or list.
Key-value lookup: Use hash table.
The Power
Graphs model complex relationships:
- BFS for shortest paths
- DFS for cycles, components, ordering
- Topological sort for dependencies
- Connected components for clustering
Understanding applications means recognizing graph patterns in real problems.
Master graph applications, and you'll solve network, dependency, and pathfinding problems efficiently.