Graph Algorithms

# Adjacency List - Like a phone book! graph = { 'A': ['B', 'C'], # A is friends with B and C 'B': ['A', 'D'], # B is friends with A and D 'C': ['A', 'D'], # C is friends with A and D 'D': ['B', 'C'] # D is friends with B and C } # Adjacency Matrix - Like a friendship grid! # A B C D matrix = [ [0, 1, 1, 0], # A's connections [1, 0, 0, 1], # B's connections [1, 0, 0, 1], # C's connections [0, 1, 1, 0] # D's connections ]

from collections import deque def bfs(graph, start): """ Breadth-First Search - Explore level by level Like ripples in water! """ visited = set([start]) queue = deque([start]) order = [] while queue: node = queue.popleft() # Take from front order.append(node) for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) queue.append(neighbor) return order # Example usage graph = { 'A': ['B', 'C'], 'B': ['D', 'E'], 'C': ['F'], 'D': [], 'E': [], 'F': [] } result = bfs(graph, 'A') # Output: ['A', 'B', 'C', 'D', 'E', 'F']

def ford_fulkerson(graph, source, sink): """ Find maximum flow from source to sink Like finding max water flow through pipes! """ def bfs_find_path(source, sink, parent): visited = set([source]) queue = [source] while queue: u = queue.pop(0) for v in graph[u]: if v not in visited and graph[u][v] > 0: visited.add(v) queue.append(v) parent[v] = u if v == sink: return True return False parent = {} max_flow = 0 while bfs_find_path(source, sink, parent): # Find minimum capacity along the path path_flow = float('inf') s = sink while s != source: path_flow = min(path_flow, graph[parent[s]][s]) s = parent[s] # Update residual capacities v = sink while v != source: u = parent[v] graph[u][v] -= path_flow graph[v][u] += path_flow v = parent[v] max_flow += path_flow parent = {} return max_flow