Table of Contents
- Introduction to Graphs
- Graph Terminology
- Types of Graphs
- Graph Representation
- Graph Traversal Algorithms
- Shortest Path Algorithms
- Minimum Spanning Tree
- Topological Sorting
- Common Graph Problems
- Advanced Topics
- Best Practices
Introduction to Graphs
A Graph is a non-linear data structure consisting of vertices (nodes) and edges that connect these vertices. Graphs are used to represent networks, relationships, and connections between entities.
Real-World Applications
- Social Networks: Facebook friends, Twitter followers
- Maps & Navigation: GPS, Google Maps (cities as nodes, roads as edges)
- Computer Networks: Routers and connections
- Web Pages: Links between pages (PageRank algorithm)
- Recommendation Systems: Netflix, Amazon
- Biology: Protein-protein interactions, neural networks
- Dependency Resolution: Package managers, build systems
Why Use Graphs?
- Model complex relationships
- Represent networks and connections
- Solve optimization problems (shortest path, minimum spanning tree)
- Analyze connectivity and reachability
- Detect cycles and patterns
Graph Terminology
Basic Concepts
A --- B
| |
| |
C --- D --- E| Term | Definition | Example |
|---|---|---|
| Vertex (Node) | A point in the graph | A, B, C, D, E |
| Edge | Connection between two vertices | A-B, C-D |
| Adjacent Vertices | Vertices connected by an edge | A and B are adjacent |
| Degree | Number of edges connected to a vertex | Degree of D is 3 |
| Path | Sequence of vertices connected by edges | A→B→D→E |
| Cycle | Path that starts and ends at same vertex | A→B→D→C→A |
| Connected Graph | Path exists between any two vertices | Above graph is connected |
| Disconnected Graph | Some vertices are not reachable | Has isolated components |
| Weighted Graph | Edges have weights/costs | Distance, cost, capacity |
| Directed Graph | Edges have direction (one-way) | A→B (can’t go B→A) |
| Undirected Graph | Edges are bidirectional | A-B (can go both ways) |
Advanced Terms
| Term | Definition |
|---|---|
| In-degree | Number of incoming edges (directed graph) |
| Out-degree | Number of outgoing edges (directed graph) |
| Self-loop | Edge from vertex to itself |
| Multi-edge | Multiple edges between same vertices |
| Simple Graph | No self-loops or multi-edges |
| Complete Graph | Edge between every pair of vertices |
| Subgraph | Graph formed by subset of vertices and edges |
| Spanning Tree | Subgraph that includes all vertices (no cycles) |
| Strongly Connected | Path exists between all vertex pairs (directed) |
| Weakly Connected | Connected if you ignore edge direction |
Types of Graphs
1. Undirected Graph
Edges have no direction (bidirectional).
# A --- B
# | |
# C --- D
graph = {
'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A', 'D'],
'D': ['B', 'C']
}2. Directed Graph (Digraph)
Edges have direction (one-way).
# A → B
# ↓ ↓
# C → D
graph = {
'A': ['B', 'C'],
'B': ['D'],
'C': ['D'],
'D': []
}3. Weighted Graph
Edges have weights/costs.
# A --5-- B
# | |
# 3 2
# | |
# C --1-- D
graph = {
'A': [('B', 5), ('C', 3)],
'B': [('A', 5), ('D', 2)],
'C': [('A', 3), ('D', 1)],
'D': [('B', 2), ('C', 1)]
}4. Cyclic vs Acyclic
- Cyclic: Contains at least one cycle
- Acyclic: No cycles (DAG = Directed Acyclic Graph)
5. Connected vs Disconnected
- Connected: Path exists between all vertex pairs
- Disconnected: Multiple separate components
Graph Representation
Method 1: Adjacency Matrix
2D array where matrix[i][j] represents edge from vertex i to vertex j.
class GraphMatrix:
"""Graph using adjacency matrix"""
def __init__(self, num_vertices, directed=False):
self.num_vertices = num_vertices
self.directed = directed
self.matrix = [[0] * num_vertices for _ in range(num_vertices)]
def add_edge(self, u, v, weight=1):
"""Add edge from u to v"""
self.matrix[u][v] = weight
if not self.directed:
self.matrix[v][u] = weight
def remove_edge(self, u, v):
"""Remove edge from u to v"""
self.matrix[u][v] = 0
if not self.directed:
self.matrix[v][u] = 0
def has_edge(self, u, v):
"""Check if edge exists"""
return self.matrix[u][v] != 0
def get_neighbors(self, vertex):
"""Get all neighbors of vertex"""
neighbors = []
for i in range(self.num_vertices):
if self.matrix[vertex][i] != 0:
neighbors.append(i)
return neighbors
def display(self):
"""Display adjacency matrix"""
for row in self.matrix:
print(row)
# Example usage
graph = GraphMatrix(4, directed=False)
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 3)
graph.add_edge(2, 3)
print("Adjacency Matrix:")
graph.display()
# [0, 1, 1, 0]
# [1, 0, 0, 1]
# [1, 0, 0, 1]
# [0, 1, 1, 0]Pros:
- O(1) edge lookup
- Simple to implement
- Good for dense graphs
Cons:
- O(V²) space (wasteful for sparse graphs)
- O(V) to get all neighbors
Method 2: Adjacency List
Dictionary/list where each vertex maps to list of neighbors.
from collections import defaultdict
class Graph:
"""Graph using adjacency list (RECOMMENDED)"""
def __init__(self, directed=False):
self.graph = defaultdict(list)
self.directed = directed
def add_vertex(self, vertex):
"""Add vertex to graph"""
if vertex not in self.graph:
self.graph[vertex] = []
def add_edge(self, u, v, weight=None):
"""Add edge from u to v"""
if weight is None:
self.graph[u].append(v)
if not self.directed:
self.graph[v].append(u)
else:
self.graph[u].append((v, weight))
if not self.directed:
self.graph[v].append((u, weight))
def remove_edge(self, u, v):
"""Remove edge from u to v"""
if v in self.graph[u]:
self.graph[u].remove(v)
if not self.directed and u in self.graph[v]:
self.graph[v].remove(u)
def has_edge(self, u, v):
"""Check if edge exists"""
return v in self.graph[u]
def get_neighbors(self, vertex):
"""Get all neighbors of vertex"""
return self.graph[vertex]
def get_vertices(self):
"""Get all vertices"""
return list(self.graph.keys())
def get_edges(self):
"""Get all edges"""
edges = []
for u in self.graph:
for v in self.graph[u]:
if self.directed or u <= v: # Avoid duplicates in undirected
edges.append((u, v))
return edges
def degree(self, vertex):
"""Get degree of vertex"""
return len(self.graph[vertex])
def display(self):
"""Display adjacency list"""
for vertex in self.graph:
print(f"{vertex}: {self.graph[vertex]}")
# Example usage
graph = Graph(directed=False)
graph.add_edge('A', 'B')
graph.add_edge('A', 'C')
graph.add_edge('B', 'D')
graph.add_edge('C', 'D')
print("Adjacency List:")
graph.display()
# A: ['B', 'C']
# B: ['A', 'D']
# C: ['A', 'D']
# D: ['B', 'C']Pros:
- O(V + E) space (efficient for sparse graphs)
- O(1) to add edge
- Fast neighbor iteration
Cons:
- O(V) edge lookup in worst case
- More complex for some operations
Method 3: Edge List
List of all edges in the graph.
class GraphEdgeList:
"""Graph using edge list"""
def __init__(self, num_vertices, directed=False):
self.num_vertices = num_vertices
self.directed = directed
self.edges = []
def add_edge(self, u, v, weight=1):
"""Add edge"""
self.edges.append((u, v, weight))
if not self.directed:
self.edges.append((v, u, weight))
def has_edge(self, u, v):
"""Check if edge exists"""
for edge in self.edges:
if edge[0] == u and edge[1] == v:
return True
return False
def display(self):
"""Display all edges"""
for u, v, w in self.edges:
print(f"{u} -> {v} (weight: {w})")
# Example usage
graph = GraphEdgeList(4, directed=True)
graph.add_edge(0, 1, 5)
graph.add_edge(1, 2, 3)
graph.add_edge(2, 3, 1)
graph.display()Pros:
- Simple to implement
- Good for algorithms that process edges sequentially
- Efficient for Kruskal’s MST algorithm
Cons:
- O(E) edge lookup
- O(E) to find neighbors
- Less efficient for most operations
Graph Traversal Algorithms
1. Breadth-First Search (BFS)
Explores graph level by level using a queue.
from collections import deque
def bfs(graph, start):
"""
Breadth-First Search traversal
Time: O(V + E)
Space: O(V)
"""
visited = set()
queue = deque([start])
visited.add(start)
result = []
while queue:
vertex = queue.popleft()
result.append(vertex)
for neighbor in graph[vertex]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return result
def bfs_with_levels(graph, start):
"""BFS with level tracking"""
visited = {start: 0}
queue = deque([start])
levels = {start: 0}
while queue:
vertex = queue.popleft()
for neighbor in graph[vertex]:
if neighbor not in visited:
visited.add(neighbor)
levels[neighbor] = levels[vertex] + 1
queue.append(neighbor)
return levels
def bfs_shortest_path(graph, start, goal):
"""Find shortest path using BFS"""
if start == goal:
return [start]
visited = {start}
queue = deque([(start, [start])])
while queue:
vertex, path = queue.popleft()
for neighbor in graph[vertex]:
if neighbor == goal:
return path + [neighbor]
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, path + [neighbor]))
return None # No path found
# Example
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
print("BFS from A:", bfs(graph, 'A'))
# Output: ['A', 'B', 'C', 'D', 'E', 'F']
print("Shortest path A to F:", bfs_shortest_path(graph, 'A', 'F'))
# Output: ['A', 'C', 'F']2. Depth-First Search (DFS)
Explores graph deeply before backtracking using recursion or stack.
def dfs_recursive(graph, start, visited=None):
"""
Depth-First Search (recursive)
Time: O(V + E)
Space: O(V)
"""
if visited is None:
visited = set()
visited.add(start)
result = [start]
for neighbor in graph[start]:
if neighbor not in visited:
result.extend(dfs_recursive(graph, neighbor, visited))
return result
def dfs_iterative(graph, start):
"""Depth-First Search (iterative)"""
visited = set()
stack = [start]
result = []
while stack:
vertex = stack.pop()
if vertex not in visited:
visited.add(vertex)
result.append(vertex)
# Add neighbors in reverse to maintain left-to-right order
for neighbor in reversed(graph[vertex]):
if neighbor not in visited:
stack.append(neighbor)
return result
def dfs_with_path(graph, start, goal, path=None, visited=None):
"""DFS to find path between two vertices"""
if path is None:
path = []
if visited is None:
visited = set()
path = path + [start]
if start == goal:
return path
visited.add(start)
for neighbor in graph[start]:
if neighbor not in visited:
new_path = dfs_with_path(graph, neighbor, goal, path, visited)
if new_path:
return new_path
return None
def dfs_all_paths(graph, start, goal, path=None, visited=None):
"""Find all paths between two vertices"""
if path is None:
path = []
if visited is None:
visited = set()
path = path + [start]
if start == goal:
return [path]
visited.add(start)
paths = []
for neighbor in graph[start]:
if neighbor not in visited:
new_paths = dfs_all_paths(graph, neighbor, goal, path, visited.copy())
paths.extend(new_paths)
return paths
# Example
print("DFS from A:", dfs_recursive(graph, 'A'))
# Output: ['A', 'B', 'D', 'E', 'F', 'C']
print("Path A to F:", dfs_with_path(graph, 'A', 'F'))
# Output: ['A', 'B', 'E', 'F']
print("All paths A to F:", dfs_all_paths(graph, 'A', 'F'))
# Output: [['A', 'B', 'E', 'F'], ['A', 'C', 'F']]3. BFS vs DFS Comparison
| Aspect | BFS | DFS |
|---|---|---|
| Data Structure | Queue | Stack/Recursion |
| Strategy | Level by level | Deep first |
| Shortest Path | ✓ (unweighted) | ✗ |
| Memory | More (stores level) | Less (stores path) |
| Completeness | ✓ | ✓ |
| Use Cases | Shortest path, level order | Topological sort, cycle detection |
Shortest Path Algorithms
1. Dijkstra’s Algorithm
Find shortest path from source to all vertices (non-negative weights).
import heapq
def dijkstra(graph, start):
"""
Dijkstra's shortest path algorithm
Time: O((V + E) log V)
Space: O(V)
Works only with non-negative weights
"""
distances = {vertex: float('inf') for vertex in graph}
distances[start] = 0
# Priority queue: (distance, vertex)
pq = [(0, start)]
visited = set()
while pq:
current_dist, current = heapq.heappop(pq)
if current in visited:
continue
visited.add(current)
# Check neighbors
for neighbor, weight in graph[current]:
distance = current_dist + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(pq, (distance, neighbor))
return distances
def dijkstra_with_path(graph, start, end):
"""Dijkstra with path reconstruction"""
distances = {vertex: float('inf') for vertex in graph}
distances[start] = 0
previous = {vertex: None for vertex in graph}
pq = [(0, start)]
visited = set()
while pq:
current_dist, current = heapq.heappop(pq)
if current == end:
break
if current in visited:
continue
visited.add(current)
for neighbor, weight in graph[current]:
distance = current_dist + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
previous[neighbor] = current
heapq.heappush(pq, (distance, neighbor))
# Reconstruct path
path = []
current = end
while current is not None:
path.append(current)
current = previous[current]
path.reverse()
return distances[end], path if path[0] == start else []
# Example
weighted_graph = {
'A': [('B', 4), ('C', 2)],
'B': [('A', 4), ('C', 1), ('D', 5)],
'C': [('A', 2), ('B', 1), ('D', 8), ('E', 10)],
'D': [('B', 5), ('C', 8), ('E', 2)],
'E': [('C', 10), ('D', 2)]
}
distances = dijkstra(weighted_graph, 'A')
print("Shortest distances from A:", distances)
# Output: {'A': 0, 'B': 3, 'C': 2, 'D': 8, 'E': 10}
dist, path = dijkstra_with_path(weighted_graph, 'A', 'E')
print(f"Shortest path A to E: {path} (distance: {dist})")
# Output: Shortest path A to E: ['A', 'C', 'B', 'D', 'E'] (distance: 10)2. Bellman-Ford Algorithm
Find shortest path with negative weights (detects negative cycles).
def bellman_ford(graph, start):
"""
Bellman-Ford algorithm (handles negative weights)
Time: O(V * E)
Space: O(V)
Returns: (distances, has_negative_cycle)
"""
# Get all vertices
vertices = set()
edges = []
for u in graph:
vertices.add(u)
for v, weight in graph[u]:
vertices.add(v)
edges.append((u, v, weight))
# Initialize distances
distances = {v: float('inf') for v in vertices}
distances[start] = 0
# Relax edges V-1 times
for _ in range(len(vertices) - 1):
for u, v, weight in edges:
if distances[u] != float('inf') and distances[u] + weight < distances[v]:
distances[v] = distances[u] + weight
# Check for negative cycles
for u, v, weight in edges:
if distances[u] != float('inf') and distances[u] + weight < distances[v]:
return distances, True # Negative cycle detected
return distances, False
# Example with negative weights
graph_negative = {
'A': [('B', 4), ('C', 2)],
'B': [('C', -3), ('D', 2)],
'C': [('D', 3)],
'D': []
}
distances, has_cycle = bellman_ford(graph_negative, 'A')
print("Distances:", distances)
print("Has negative cycle:", has_cycle)3. Floyd-Warshall Algorithm
Find shortest paths between all pairs of vertices.
def floyd_warshall(graph):
"""
Floyd-Warshall algorithm (all pairs shortest path)
Time: O(V³)
Space: O(V²)
"""
# Get all vertices
vertices = list(graph.keys())
n = len(vertices)
vertex_to_idx = {v: i for i, v in enumerate(vertices)}
# Initialize distance matrix
dist = [[float('inf')] * n for _ in range(n)]
# Distance from vertex to itself is 0
for i in range(n):
dist[i][i] = 0
# Fill in edge weights
for u in graph:
i = vertex_to_idx[u]
for v, weight in graph[u]:
j = vertex_to_idx[v]
dist[i][j] = weight
# Floyd-Warshall main loop
for k in range(n):
for i in range(n):
for j in range(n):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
# Convert back to vertex names
result = {}
for i, u in enumerate(vertices):
result[u] = {}
for j, v in enumerate(vertices):
result[u][v] = dist[i][j]
return result
# Example
distances = floyd_warshall(weighted_graph)
print("All pairs shortest paths:")
for u in distances:
print(f"From {u}: {distances[u]}")4. A* Search Algorithm
Heuristic-based shortest path (faster than Dijkstra for specific goals).
def a_star(graph, start, goal, heuristic):
"""
A* search algorithm
Time: O(E log V) in practice
heuristic: function(node) -> estimated distance to goal
"""
open_set = [(0, start)] # (f_score, vertex)
came_from = {}
g_score = {vertex: float('inf') for vertex in graph}
g_score[start] = 0
f_score = {vertex: float('inf') for vertex in graph}
f_score[start] = heuristic(start)
while open_set:
_, current = heapq.heappop(open_set)
if current == goal:
# Reconstruct path
path = [current]
while current in came_from:
current = came_from[current]
path.append(current)
return path[::-1]
for neighbor, weight in graph[current]:
tentative_g = g_score[current] + weight
if tentative_g < g_score[neighbor]:
came_from[neighbor] = current
g_score[neighbor] = tentative_g
f_score[neighbor] = tentative_g + heuristic(neighbor)
heapq.heappush(open_set, (f_score[neighbor], neighbor))
return None # No path found
# Example with grid coordinates as heuristic
def manhattan_distance(node):
"""Example heuristic for grid-based graph"""
# Assuming node format is (x, y) and goal is (5, 5)
goal = (5, 5)
return abs(node[0] - goal[0]) + abs(node[1] - goal[1])Minimum Spanning Tree
A spanning tree that connects all vertices with minimum total edge weight.
1. Kruskal’s Algorithm
Greedy algorithm using Union-Find (sorts edges).
class UnionFind:
"""Union-Find (Disjoint Set Union) data structure"""
def __init__(self, vertices):
self.parent = {v: v for v in vertices}
self.rank = {v: 0 for v in vertices}
def find(self, vertex):
"""Find root with path compression"""
if self.parent[vertex] != vertex:
self.parent[vertex] = self.find(self.parent[vertex])
return self.parent[vertex]
def union(self, u, v):
"""Union by rank"""
root_u = self.find(u)
root_v = self.find(v)
if root_u == root_v:
return False
if self.rank[root_u] < self.rank[root_v]:
self.parent[root_u] = root_v
elif self.rank[root_u] > self.rank[root_v]:
self.parent[root_v] = root_u
else:
self.parent[root_v] = root_u
self.rank[root_u] += 1
return True
def kruskal_mst(vertices, edges):
"""
Kruskal's Minimum Spanning Tree algorithm
Time: O(E log E)
Space: O(V)
Args:
vertices: list of vertices
edges: list of (u, v, weight) tuples
Returns:
List of edges in MST and total weight
"""
# Sort edges by weight
edges = sorted(edges, key=lambda x: x[2])
uf = UnionFind(vertices)
mst = []
total_weight = 0
for u, v, weight in edges:
# If u and v are in different components, add edge
if uf.union(u, v):
mst.append((u, v, weight))
total_weight += weight
# MST complete when we have V-1 edges
if len(mst) == len(vertices) - 1:
break
return mst, total_weight
# Example
vertices = ['A', 'B', 'C', 'D', 'E']
edges = [
('A', 'B', 4),
('A', 'C', 2),
('B', 'C', 1),
('B', 'D', 5),
('C', 'D', 8),
('C', 'E', 10),
('D', 'E', 2)
]
mst, weight = kruskal_mst(vertices, edges)
print("Kruskal's MST:")
for u, v, w in mst:
print(f"{u} - {v}: {w}")
print(f"Total weight: {weight}")2. Prim’s Algorithm
Greedy algorithm that grows MST from starting vertex.
def prim_mst(graph, start):
"""
Prim's Minimum Spanning Tree algorithm
Time: O(E log V)
Space: O(V)
Args:
graph: adjacency list with weights
start: starting vertex
Returns:
List of edges in MST and total weight
"""
visited = set([start])
mst = []
total_weight = 0
# Priority queue: (weight, from, to)
pq = [(weight, start, neighbor) for neighbor, weight in graph[start]]
heapq.heapify(pq)
while pq and len(visited) < len(graph):
weight, u, v = heapq.heappop(pq)
if v in visited:
continue
visited.add(v)
mst.append((u, v, weight))
total_weight += weight
# Add edges from newly added vertex
for neighbor, w in graph[v]:
if neighbor not in visited:
heapq.heappush(pq, (w, v, neighbor))
return mst, total_weight
# Example
mst, weight = prim_mst(weighted_graph, 'A')
print("Prim's MST:")
for u, v, w in mst:
print(f"{u} - {v}: {w}")
print(f"Total weight: {weight}")Topological Sorting
Linear ordering of vertices in DAG where u comes before v for every edge u→v.
1. DFS-based Topological Sort
def topological_sort_dfs(graph):
"""
Topological sort using DFS
Time: O(V + E)
Space: O(V)
Works only for DAG (Directed Acyclic Graph)
"""
visited = set()
stack = []
def dfs(vertex):
visited.add(vertex)
for neighbor in graph.get(vertex, []):
if neighbor not in visited:
dfs(neighbor)
stack.append(vertex)
# Visit all vertices
for vertex in graph:
if vertex not in visited:
dfs(vertex)
return stack[::-1]
# Example: Task dependencies
tasks = {
'A': ['C'],
'B': ['C', 'D'],
'C': ['E'],
'D': ['E'],
'E': []
}
print("Topological order:", topological_sort_dfs(tasks))
# Output: ['B', 'A', 'D', 'C', 'E'] or ['A', 'B', 'C', 'D', 'E']2. Kahn’s Algorithm (BFS-based)
from collections import deque, defaultdict
def topological_sort_kahn(graph):
"""
Topological sort using Kahn's algorithm (BFS)
Time: O(V + E)
Space: O(V)
Returns None if graph has cycle
"""
# Calculate in-degree for each vertex
in_degree = defaultdict(int)
for vertex in graph:
if vertex not in in_degree:
in_degree[vertex] = 0
for neighbor in graph[vertex]:
in_degree[neighbor] += 1
# Queue of vertices with in-degree 0
queue = deque([v for v in in_degree if in_degree[v] == 0])
result = []
while queue:
vertex = queue.popleft()
result.append(vertex)
# Reduce in-degree of neighbors
for neighbor in graph[vertex]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
# Check if all vertices were processed
if len(result) != len(in_degree):
return None # Cycle detected
return result
print("Topological order (Kahn):", topological_sort_kahn(tasks))Common Graph Problems
1. Detect Cycle in Graph
def has_cycle_undirected(graph):
"""Detect cycle in undirected graph using DFS"""
visited = set()
def dfs(vertex, parent):
visited.add(vertex)
for neighbor in graph[vertex]:
if neighbor not in visited:
if dfs(neighbor, vertex):
return True
elif neighbor != parent:
return True # Back edge found
return False
# Check all components
for vertex in graph:
if vertex not in visited:
if dfs(vertex, None):
return True
return False
def has_cycle_directed(graph):
"""Detect cycle in directed graph using DFS"""
WHITE, GRAY, BLACK = 0, 1, 2
color = {vertex: WHITE for vertex in graph}
def dfs(vertex):
color[vertex] = GRAY
for neighbor in graph.get(vertex, []):
if color[neighbor] == GRAY:
return True # Back edge (cycle)
if color[neighbor] == WHITE and dfs(neighbor):
return True
color[vertex] = BLACK
return False
for vertex in graph:
if color[vertex] == WHITE:
if dfs(vertex):
return True
return False
# Test
undirected_cycle = {
'A': ['B'],
'B': ['A', 'C'],
'C': ['B', 'A'] # Creates cycle
}
print("Undirected has cycle:", has_cycle_undirected(undirected_cycle))2. Number of Connected Components
def count_components(graph):
"""Count connected components in undirected graph"""
visited = set()
count = 0
def dfs(vertex):
visited.add(vertex)
for neighbor in graph[vertex]:
if neighbor not in visited:
dfs(neighbor)
for vertex in graph:
if vertex not in visited:
dfs(vertex)
count += 1
return count
# Test
disconnected = {
'A': ['B'],
'B': ['A'],
'C': ['D'],
'D': ['C'],
'E': []
}
print("Number of components:", count_components(disconnected)) # 33. Find All Bridges (Cut Edges)
def find_bridges(graph):
"""
Find all bridges in undirected graph
Bridge: edge whose removal increases number of components
Time: O(V + E)
"""
discovery = {}
low = {}
parent = {}
bridges = []
time = [0]
def dfs(u):
discovery[u] = low[u] = time[0]
time[0] += 1
for v in graph[u]:
if v not in discovery:
parent[v] = u
dfs(v)
low[u] = min(low[u], low[v])
# Bridge condition
if low[v] > discovery[u]:
bridges.append((u, v))
elif v != parent.get(u):
low[u] = min(low[u], discovery[v])
for vertex in graph:
if vertex not in discovery:
parent[vertex] = None
dfs(vertex)
return bridges
# Test
bridge_graph = {
'A': ['B', 'C'],
'B': ['A', 'C'],
'C': ['A', 'B', 'D'],
'D': ['C']
}
print("Bridges:", find_bridges(bridge_graph)) # [('C', 'D')]4. Find Articulation Points (Cut Vertices)
def find_articulation_points(graph):
"""
Find all articulation points
Articulation point: vertex whose removal increases components
Time: O(V + E)
"""
discovery = {}
low = {}
parent = {}
articulation_points = set()
time = [0]
def dfs(u):
children = 0
discovery[u] = low[u] = time[0]
time[0] += 1
for v in graph[u]:
if v not in discovery:
children += 1
parent[v] = u
dfs(v)
low[u] = min(low[u], low[v])
# Articulation point conditions
if parent[u] is None and children > 1:
articulation_points.add(u)
if parent[u] is not None and low[v] >= discovery[u]:
articulation_points.add(u)
elif v != parent.get(u):
low[u] = min(low[u], discovery[v])
for vertex in graph:
if vertex not in discovery:
parent[vertex] = None
dfs(vertex)
return list(articulation_points)
print("Articulation points:", find_articulation_points(bridge_graph))5. Clone Graph (LeetCode #133)
class Node:
def __init__(self, val=0, neighbors=None):
self.val = val
self.neighbors = neighbors if neighbors is not None else []
def clone_graph(node):
"""Clone an undirected graph"""
if not node:
return None
clones = {}
def dfs(n):
if n in clones:
return clones[n]
clone = Node(n.val)
clones[n] = clone
for neighbor in n.neighbors:
clone.neighbors.append(dfs(neighbor))
return clone
return dfs(node)6. Course Schedule (LeetCode #207)
def can_finish(num_courses, prerequisites):
"""
Determine if you can finish all courses
(Cycle detection in directed graph)
Example: numCourses=2, prerequisites=[[1,0]]
To take course 1, must take course 0 first
"""
# Build graph
graph = defaultdict(list)
for course, prereq in prerequisites:
graph[prereq].append(course)
# 0=unvisited, 1=visiting, 2=visited
state = [0] * num_courses
def has_cycle(course):
if state[course] == 1:
return True # Cycle detected
if state[course] == 2:
return False # Already checked
state[course] = 1
for next_course in graph[course]:
if has_cycle(next_course):
return True
state[course] = 2
return False
for course in range(num_courses):
if has_cycle(course):
return False
return True
# Test
print(can_finish(2, [[1, 0]])) # True
print(can_finish(2, [[1, 0], [0, 1]])) # False (cycle)7. Number of Islands (LeetCode #200)
def num_islands(grid):
"""
Count number of islands in 2D grid
1 = land, 0 = water
"""
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
count = 0
def dfs(r, c):
if (r < 0 or r >= rows or c < 0 or c >= cols or
grid[r][c] == '0'):
return
grid[r][c] = '0' # Mark as visited
# Check 4 directions
dfs(r + 1, c)
dfs(r - 1, c)
dfs(r, c + 1)
dfs(r, c - 1)
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
dfs(r, c)
count += 1
return count
# Test
grid = [
['1', '1', '0', '0', '0'],
['1', '1', '0', '0', '0'],
['0', '0', '1', '0', '0'],
['0', '0', '0', '1', '1']
]
print("Number of islands:", num_islands(grid)) # 38. Word Ladder (LeetCode #127)
def word_ladder(begin_word, end_word, word_list):
"""
Find shortest transformation sequence length
Example: beginWord="hit", endWord="cog"
wordList=["hot","dot","dog","lot","log","cog"]
Output: 5 ("hit"->"hot"->"dot"->"dog"->"cog")
"""
if end_word not in word_list:
return 0
word_set = set(word_list)
queue = deque([(begin_word, 1)])
while queue:
word, length = queue.popleft()
if word == end_word:
return length
# Try all possible one-letter changes
for i in range(len(word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
next_word = word[:i] + c + word[i+1:]
if next_word in word_set:
word_set.remove(next_word)
queue.append((next_word, length + 1))
return 0
# Test
print(word_ladder("hit", "cog", ["hot","dot","dog","lot","log","cog"])) # 59. Network Delay Time (LeetCode #743)
def network_delay_time(times, n, k):
"""
Find time for signal to reach all nodes
times = [[source, target, time]]
"""
graph = defaultdict(list)
for u, v, w in times:
graph[u].append((v, w))
# Dijkstra's algorithm
distances = {i: float('inf') for i in range(1, n + 1)}
distances[k] = 0
pq = [(0, k)]
while pq:
time, node = heapq.heappop(pq)
if time > distances[node]:
continue
for neighbor, t in graph[node]:
new_time = time + t
if new_time < distances[neighbor]:
distances[neighbor] = new_time
heapq.heappush(pq, (new_time, neighbor))
max_time = max(distances.values())
return max_time if max_time != float('inf') else -1Advanced Topics
1. Strongly Connected Components (Kosaraju’s Algorithm)
def kosaraju_scc(graph):
"""
Find all strongly connected components
Time: O(V + E)
"""
# Step 1: Fill order of vertices (DFS on original graph)
visited = set()
stack = []
def dfs1(vertex):
visited.add(vertex)
for neighbor in graph.get(vertex, []):
if neighbor not in visited:
dfs1(neighbor)
stack.append(vertex)
for vertex in graph:
if vertex not in visited:
dfs1(vertex)
# Step 2: Create transpose graph
transpose = defaultdict(list)
for u in graph:
for v in graph[u]:
transpose[v].append(u)
# Step 3: DFS on transpose in reverse order
visited = set()
sccs = []
def dfs2(vertex, component):
visited.add(vertex)
component.append(vertex)
for neighbor in transpose.get(vertex, []):
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
# Test
directed_graph = {
'A': ['B'],
'B': ['C', 'E'],
'C': ['D'],
'D': ['B'],
'E': ['F'],
'F': ['E']
}
print("SCCs:", kosaraju_scc(directed_graph))
# Output: [['F', 'E'], ['D', 'C', 'B'], ['A']]2. Tarjan’s Algorithm (SCC)
def tarjan_scc(graph):
"""
Find SCCs using Tarjan's algorithm (single DFS)
Time: O(V + E)
"""
index_counter = [0]
stack = []
lowlinks = {}
index = {}
on_stack = set()
sccs = []
def strongconnect(v):
index[v] = index_counter[0]
lowlinks[v] = index_counter[0]
index_counter[0] += 1
stack.append(v)
on_stack.add(v)
for w in graph.get(v, []):
if w not in index:
strongconnect(w)
lowlinks[v] = min(lowlinks[v], lowlinks[w])
elif w in on_stack:
lowlinks[v] = min(lowlinks[v], index[w])
if lowlinks[v] == index[v]:
component = []
while True:
w = stack.pop()
on_stack.remove(w)
component.append(w)
if w == v:
break
sccs.append(component)
for v in graph:
if v not in index:
strongconnect(v)
return sccs
print("SCCs (Tarjan):", tarjan_scc(directed_graph))3. Graph Coloring
def graph_coloring(graph, num_colors):
"""
Color graph using backtracking
Returns color assignment or None if impossible
"""
vertices = list(graph.keys())
colors = {}
def is_safe(vertex, color):
for neighbor in graph[vertex]:
if neighbor in colors and colors[neighbor] == color:
return False
return True
def backtrack(vertex_idx):
if vertex_idx == len(vertices):
return True
vertex = vertices[vertex_idx]
for color in range(num_colors):
if is_safe(vertex, color):
colors[vertex] = color
if backtrack(vertex_idx + 1):
return True
del colors[vertex]
return False
if backtrack(0):
return colors
return None
# Test
coloring_graph = {
'A': ['B', 'C'],
'B': ['A', 'C', 'D'],
'C': ['A', 'B', 'D'],
'D': ['B', 'C']
}
colors = graph_coloring(coloring_graph, 3)
print("Graph coloring:", colors)4. Traveling Salesman Problem (TSP)
def tsp_brute_force(graph, start):
"""
TSP using brute force (small graphs only)
Time: O(n!)
"""
vertices = [v for v in graph if v != start]
min_path = None
min_cost = float('inf')
from itertools import permutations
for perm in permutations(vertices):
current_cost = 0
path = [start] + list(perm) + [start]
# Calculate path cost
valid = True
for i in range(len(path) - 1):
found = False
for neighbor, weight in graph[path[i]]:
if neighbor == path[i + 1]:
current_cost += weight
found = True
break
if not found:
valid = False
break
if valid and current_cost < min_cost:
min_cost = current_cost
min_path = path
return min_path, min_cost
def tsp_dp(dist, n):
"""
TSP using dynamic programming
Time: O(n² * 2ⁿ)
Space: O(n * 2ⁿ)
"""
# dp[mask][i] = min cost to visit all vertices in mask, ending at i
dp = [[float('inf')] * n for _ in range(1 << n)]
dp[1][0] = 0 # Start at vertex 0
for mask in range(1 << n):
for u in range(n):
if not (mask & (1 << u)):
continue
for v in range(n):
if mask & (1 << v):
continue
new_mask = mask | (1 << v)
dp[new_mask][v] = min(dp[new_mask][v],
dp[mask][u] + dist[u][v])
# Find minimum cost to return to start
final_mask = (1 << n) - 1
min_cost = float('inf')
for i in range(1, n):
min_cost = min(min_cost, dp[final_mask][i] + dist[i][0])
return min_cost5. Maximum Flow (Ford-Fulkerson)
def ford_fulkerson(graph, source, sink):
"""
Find maximum flow from source to sink
Time: O(E * max_flow)
"""
# Create residual graph
residual = defaultdict(lambda: defaultdict(int))
for u in graph:
for v, capacity in graph[u]:
residual[u][v] = capacity
def bfs_find_path():
"""Find augmenting path using BFS"""
visited = {source}
queue = deque([(source, [source])])
while queue:
vertex, path = queue.popleft()
for neighbor in residual[vertex]:
if neighbor not in visited and residual[vertex][neighbor] > 0:
if neighbor == sink:
return path + [neighbor]
visited.add(neighbor)
queue.append((neighbor, path + [neighbor]))
return None
max_flow = 0
while True:
path = bfs_find_path()
if not path:
break
# Find minimum capacity in path
flow = float('inf')
for i in range(len(path) - 1):
flow = min(flow, residual[path[i]][path[i + 1]])
# Update residual capacities
for i in range(len(path) - 1):
u, v = path[i], path[i + 1]
residual[u][v] -= flow
residual[v][u] += flow
max_flow += flow
return max_flow
# Test
flow_graph = {
's': [('a', 10), ('c', 10)],
'a': [('b', 4), ('c', 2), ('d', 8)],
'b': [('t', 10)],
'c': [('d', 9)],
'd': [('b', 6), ('t', 10)],
't': []
}
print("Maximum flow:", ford_fulkerson(flow_graph, 's', 't'))Best Practices
1. Choosing Graph Representation
"""
Adjacency Matrix:
✓ Dense graphs (many edges)
✓ Need O(1) edge lookup
✓ Fixed number of vertices
✗ Sparse graphs (waste space)
Adjacency List:
✓ Sparse graphs (few edges)
✓ Need to iterate neighbors
✓ Dynamic vertex addition
✗ Slower edge lookup
Edge List:
✓ Kruskal's MST
✓ Union-Find operations
✗ Most other operations
"""2. Common Patterns
Pattern 1: BFS Template
def bfs_template(graph, start):
visited = {start}
queue = deque([start])
while queue:
vertex = queue.popleft()
# Process vertex
process(vertex)
for neighbor in graph[vertex]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)Pattern 2: DFS Template
def dfs_template(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
# Process vertex
process(start)
for neighbor in graph[start]:
if neighbor not in visited:
dfs_template(graph, neighbor, visited)Pattern 3: Union-Find Template
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py:
return False
if self.rank[px] < self.rank[py]:
px, py = py, px
self.parent[py] = px
if self.rank[px] == self.rank[py]:
self.rank[px] += 1
return True3. Performance Optimization
# ✓ Use appropriate data structures
from collections import defaultdict, deque
import heapq
# ✓ Avoid redundant work
visited = set() # Track visited vertices
# ✓ Use early termination
if found_target:
return result
# ✓ Choose right algorithm
# - BFS for shortest path in unweighted graph
# - Dijkstra for weighted graph (non-negative)
# - Bellman-Ford for negative weights
# - A* for heuristic-based search4. Testing Graphs
def create_test_graph():
"""Helper to create test graphs"""
return {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
def visualize_graph(graph):
"""Simple text visualization"""
print("Graph:")
for vertex in sorted(graph.keys()):
neighbors = ', '.join(map(str, graph[vertex]))
print(f" {vertex} → [{neighbors}]")5. Type Hints
from typing import Dict, List, Set, Tuple, Optional
def dijkstra(
graph: Dict[str, List[Tuple[str, int]]],
start: str
) -> Dict[str, int]:
"""
Find shortest paths from start vertex
Args:
graph: Weighted adjacency list
start: Starting vertex
Returns:
Dictionary mapping vertices to shortest distances
"""
passSummary
Key Takeaways
- Versatile Structure: Graphs model complex relationships and networks
- Two Representations: Adjacency list (sparse), matrix (dense)
- Two Traversals: BFS (level-by-level), DFS (deep-first)
- Many Algorithms: Shortest path, MST, topological sort, etc.
- Common Patterns: BFS, DFS, Union-Find, Dynamic Programming
- Real Applications: Maps, social networks, dependencies, optimization
Algorithm Complexity Summary
| Algorithm | Time | Space | Use Case |
|---|---|---|---|
| BFS | O(V + E) | O(V) | Shortest path (unweighted) |
| DFS | O(V + E) | O(V) | Cycle detection, topological sort |
| Dijkstra | O((V+E) log V) | O(V) | Shortest path (non-negative) |
| Bellman-Ford | O(VE) | O(V) | Shortest path (negative weights) |
| Floyd-Warshall | O(V³) | O(V²) | All pairs shortest path |
| Kruskal | O(E log E) | O(V) | Minimum spanning tree |
| Prim | O(E log V) | O(V) | Minimum spanning tree |
| Topological Sort | O(V + E) | O(V) | Task scheduling |
Quick Reference
# Create graph
graph = defaultdict(list)
graph['A'].append('B')
# BFS
queue = deque([start])
while queue:
vertex = queue.popleft()
# DFS
def dfs(vertex):
visited.add(vertex)
for neighbor in graph[vertex]:
if neighbor not in visited:
dfs(neighbor)
# Dijkstra
pq = [(0, start)]
while pq:
dist, vertex = heapq.heappop(pq)Interview Preparation Checklist
Easy:
- ✓ BFS/DFS traversal
- ✓ Detect cycle
- ✓ Number of islands
- ✓ Clone graph
- ✓ Connected components
Medium:
- ✓ Course schedule
- ✓ Word ladder
- ✓ Network delay
- ✓ Topological sort
- ✓ Bridges and articulation points
Hard:
- ✓ Dijkstra/Bellman-Ford
- ✓ MST (Kruskal/Prim)
- ✓ Strongly connected components
- ✓ TSP
- ✓ Maximum flow
Further Reading
- Graph Theory Fundamentals
- Network Flow Algorithms
- Bipartite Matching
- Planar Graphs
- Eulerian and Hamiltonian Paths
- Graph Neural Networks (GNNs)
Practice Resources:
- LeetCode Graph Problems (100+)
- HackerRank Graph Challenges
- Codeforces Graph Problems
- GeeksforGeeks Graph Articles
- Graph Visualization Tools
Happy Coding! 🔗
Discover more from Altgr Blog
Subscribe to get the latest posts sent to your email.
