Introduction
Graphs are fundamental data structures that model relationships between objects. From social networks to road systems, from dependency resolution to recommendation engines, graph algorithms power many modern applications. This guide covers essential graph algorithms, their implementations, and real-world applications.
Graph Fundamentals
Types of Graphs
By Direction
- Directed: Edges have specific direction
- Undirected: Edges are bidirectional
By Weight
- Weighted: Edges have associated costs
- Unweighted: All edges equal
By Structure
- Cyclic: Contains cycles
- Acyclic: No cycles (DAG)
- Tree: Connected, acyclic
- Complete: Every node connected
Common Representations
Adjacency Matrix
# O(1) edge lookup, O(V²) space
graph = [
[0, 1, 0, 1],
[1, 0, 1, 0],
[0, 1, 0, 1],
[1, 0, 1, 0]
]
Adjacency List
# O(V + E) space, O(1) neighbor iteration
graph = {
'A': ['B', 'D'],
'B': ['A', 'C'],
'C': ['B', 'D'],
'D': ['A', 'C']
}
Traversal Algorithms
Breadth-First Search (BFS)
Explores level by level using a queue.
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
while queue:
node = queue.popleft()
print(node, end=' ')
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
Time Complexity: O(V + E) Space Complexity: O(V) Applications: Shortest path in unweighted graphs, level-order traversal
Depth-First Search (DFS)
Explores as deep as possible before backtracking.
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
print(start, end=' ')
for neighbor in graph[start]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
Time Complexity: O(V + E) Space Complexity: O(V) Applications: Cycle detection, topological sort, path finding
BFS vs DFS
| Aspect | BFS | DFS |
|---|---|---|
| Data structure | Queue | Stack/Recursion |
| Finds shortest path | Yes (unweighted) | No |
| Memory | More | Less |
| Completeness | Always | May overflow stack |
Shortest Path Algorithms
Dijkstra’s Algorithm
Finds shortest path in weighted graphs with non-negative weights.
import heapq
def dijkstra(graph, start):
distances = {node: float('inf') for node in graph}
distances[start] = 0
pq = [(0, start)]
while pq:
current_dist, current = heapq.heappop(pq)
if current_dist > distances[current]:
continue
for neighbor, weight in graph[current]:
distance = current_dist + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(pq, (distance, neighbor))
return distances
Time Complexity: O((V + E) log V) Space Complexity: O(V) Applications: GPS navigation, network routing, flight scheduling
Bellman-Ford
Handles negative edge weights.
def bellman_ford(graph, start):
distances = {node: float('inf') for node in graph}
distances[start] = 0
# Relax all edges V-1 times
for _ in range(len(graph) - 1):
for node in graph:
for neighbor, weight in graph[node]:
if distances[node] != float('inf'):
distances[neighbor] = min(
distances[neighbor],
distances[node] + weight
)
# Check for negative cycles
for node in graph:
for neighbor, weight in graph[node]:
if distances[node] != float('inf'):
if distances[node] + weight < distances[neighbor]:
return None # Negative cycle
return distances
Time Complexity: O(VE) Space Complexity: O(V)
A* Algorithm
Uses heuristics for faster pathfinding.
import heapq
def astar(graph, start, goal, heuristic):
frontier = [(0, start)]
came_from = {start: None}
cost_so_far = {start: 0}
while frontier:
current = heapq.heappop(frontier)[1]
if current == goal:
break
for neighbor in graph[current]:
new_cost = cost_so_far[current] + graph[current][neighbor]
if neighbor not in cost_so_far or new_cost < cost_so_far[neighbor]:
cost_so_far[neighbor] = new_cost
priority = new_cost + heuristic(neighbor, goal)
heapq.heappush(frontier, (priority, neighbor))
came_from[neighbor] = current
return came_from, cost_so_far
Minimum Spanning Tree
Kruskal’s Algorithm
Greedy algorithm that sorts edges by weight.
def kruskal(graph):
# Sort edges by weight
edges = []
for node in graph:
for neighbor, weight in graph[node]:
edges.append((weight, node, neighbor))
edges.sort()
parent = {node: node for node in graph}
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(x, y):
px, py = find(x), find(y)
if px != py:
parent[px] = py
return True
return False
mst = []
for weight, u, v in edges:
if union(u, v):
mst.append((u, v, weight))
return mst
Time Complexity: O(E log E) Space Complexity: O(V)
Prim’s Algorithm
Grows MST from a starting node.
import heapq
def prim(graph, start):
visited = {start}
edges = []
pq = []
for neighbor, weight in graph[start]:
heapq.heappush(pq, (weight, start, neighbor))
while pq and len(visited) < len(graph):
weight, u, v = heapq.heappop(pq)
if v in visited:
continue
visited.add(v)
edges.append((u, v, weight))
for neighbor, w in graph[v]:
if neighbor not in visited:
heapq.heappush(pq, (w, v, neighbor))
return edges
Graph Coloring
Greedy Coloring
def greedy_color(graph):
colors = {}
for node in graph:
neighbor_colors = {colors[neighbor] for neighbor in graph[node] if neighbor in colors}
color = 0
while color in neighbor_colors:
color += 1
colors[node] = color
return colors
Topological Sort
Ordering vertices in a DAG.
def topological_sort(graph):
visited = set()
result = []
def dfs(node):
if node in visited:
return
visited.add(node)
for neighbor in graph[node]:
dfs(neighbor)
result.append(node)
for node in graph:
dfs(node)
return result[::-1]
Strongly Connected Components
Kosaraju’s Algorithm
def kosaraju(graph):
# First DFS to get finishing order
visited = set()
order = []
def dfs(node):
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs(neighbor)
order.append(node)
for node in graph:
if node not in visited:
dfs(node)
# Reverse graph
reverse = {node: [] for node in graph}
for node in graph:
for neighbor in graph[node]:
reverse[neighbor].append(node)
# Second DFS on reverse graph
visited.clear()
components = []
def dfs_rev(node, component):
visited.add(node)
component.append(node)
for neighbor in reverse[node]:
if neighbor not in visited:
dfs_rev(neighbor, component)
for node in reversed(order):
if node not in visited:
component = []
dfs_rev(node, component)
components.append(component)
return components
Real-World Applications
Social Networks
- Friend recommendations
- Influence analysis
- Community detection
- Path finding (degrees of separation)
Navigation
- GPS routing
- Traffic analysis
- Delivery optimization
Web
- PageRank algorithm
- Web crawling
- Link analysis
Dependency Management
- Package managers
- Build systems
- Task scheduling
Conclusion
Graph algorithms are essential tools for solving relationship-based problems. Understanding when to use each algorithm—BFS for shortest paths in unweighted graphs, Dijkstra for weighted graphs, or DFS for cycle detection—enables effective problem-solving. These algorithms form the backbone of many modern applications, from social networks to logistics.
Comments