Graph Algorithms Proficient¶

from collections import defaultdict, deque

# Adjacency list (most common)
graph = defaultdict(list)
graph["A"].extend(["B", "C"])
graph["B"].extend(["D", "E"])
graph["C"].extend(["F"])
# A → B, C
# B → D, E
# C → F

# Weighted graph
weighted = defaultdict(list)
weighted["A"].append(("B", 4))
weighted["A"].append(("C", 2))
weighted["B"].append(("D", 3))

def bfs(graph, start, target):
    """Find shortest path from start to target."""
    queue = deque([(start, [start])])
    visited = {start}

    while queue:
        node, path = queue.popleft()
        if node == target:
            return path

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))

    return None   # no path found

path = bfs(graph, "A", "F")
print(path)   # ['A', 'C', 'F']

def dfs(graph, start, target, visited=None):
    """Find if path exists (recursive)."""
    if visited is None:
        visited = set()
    if start == target:
        return True
    visited.add(start)
    for neighbor in graph[start]:
        if neighbor not in visited:
            if dfs(graph, neighbor, target, visited):
                return True
    return False

# Iterative DFS
def dfs_iterative(graph, start):
    """Visit all nodes reachable from start."""
    stack = [start]
    visited = set()
    order = []

    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                stack.append(neighbor)

    return order

import heapq

def dijkstra(graph, start):
    """Find shortest distance from start to all nodes."""
    distances = {start: 0}
    priority_queue = [(0, start)]

    while priority_queue:
        dist, node = heapq.heappop(priority_queue)
        if dist > distances.get(node, float('inf')):
            continue

        for neighbor, weight in graph[node]:
            new_dist = dist + weight
            if new_dist < distances.get(neighbor, float('inf')):
                distances[neighbor] = new_dist
                heapq.heappush(priority_queue, (new_dist, neighbor))

    return distances

distances = dijkstra(weighted, "A")
print(distances)   # {'A': 0, 'C': 2, 'B': 4, 'D': 7}

def topological_sort(graph):
    """Kahn's algorithm — BFS-based topological sort."""
    in_degree = defaultdict(int)
    for node in graph:
        for neighbor in graph[node]:
            in_degree[neighbor] += 1

    queue = deque([n for n in graph if in_degree[n] == 0])
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    if len(order) != len(graph):
        raise ValueError("Graph has a cycle!")
    return order

# Task dependencies
tasks = defaultdict(list)
tasks["build"].append("test")
tasks["test"].append("deploy")
tasks["lint"].append("build")
print(topological_sort(tasks))   # ['lint', 'build', 'test', 'deploy']

def has_cycle(graph):
    """Detect cycle using DFS coloring."""
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {node: WHITE for node in graph}

    def dfs(node):
        color[node] = GRAY
        for neighbor in graph[node]:
            if color[neighbor] == GRAY:   # back edge = cycle!
                return True
            if color[neighbor] == WHITE and dfs(neighbor):
                return True
        color[node] = BLACK
        return False

    return any(dfs(node) for node in graph if color[node] == WHITE)