Chapter 09: Graphs ⭐⭐

# Using a dictionary of lists
adjacency_list = {
    "A": ["B", "C"],
    "B": ["A", "C", "D"],
    "C": ["A", "B", "D"],
    "D": ["B", "C"],
}

# Using defaultdict (avoids KeyError for missing nodes)
from collections import defaultdict
graph = defaultdict(list)
edges = [("A", "B"), ("A", "C"), ("B", "C"), ("B", "D"), ("C", "D")]
for source, destination in edges:
    graph[source].append(destination)
    graph[destination].append(source)  # Undirected → add both directions

# For nodes A=0, B=1, C=2, D=3
# matrix[i][j] = 1 means edge from i to j
adjacency_matrix = [
    # A  B  C  D
    [0, 1, 1, 0],  # A: connected to B, C
    [1, 0, 1, 1],  # B: connected to A, C, D
    [1, 1, 0, 1],  # C: connected to A, B, D
    [0, 1, 1, 0],  # D: connected to B, C
]

# Check if A and B are connected:
# adjacency_matrix[0][1] → 1 (yes)

# For WEIGHTED graphs, store the weight instead of 1:
weighted_matrix = [
    [0,   5,   3,   0],  # A→B costs 5, A→C costs 3
    [5,   0,   2,   7],  # B→A costs 5, B→C costs 2, B→D costs 7
    [3,   2,   0,   4],
    [0,   7,   4,   0],
]

class GraphNode:
    def __init__(self, value):
        self.value = value
        self.neighbors = []  # List of GraphNode references

# Build the graph
node_a = GraphNode("A")
node_b = GraphNode("B")
node_c = GraphNode("C")
node_d = GraphNode("D")

# Add edges (undirected = both directions)
node_a.neighbors.extend([node_b, node_c])
node_b.neighbors.extend([node_a, node_c, node_d])
node_c.neighbors.extend([node_a, node_b, node_d])
node_d.neighbors.extend([node_b, node_c])

from collections import deque

def bfs(graph: dict, start: str) -> list[str]:
    """
    BFS on a graph using adjacency list representation.

    Visits nodes level by level (closest first).
    Uses a QUEUE (deque) — FIFO order.

    Time: O(V + E)  — visit each vertex once, examine each edge once
    Space: O(V)     — visited set + queue can hold up to V nodes
    """
    visited = set()        # Track visited nodes to avoid cycles. O(1) lookup.
    queue = deque([start]) # BFS queue — FIFO order
    visited.add(start)     # Mark start as visited BEFORE entering loop
    result = []

    while queue:
        node = queue.popleft()  # O(1) — deque advantage!
        result.append(node)

        # Explore all neighbors
        for neighbor in graph[node]:        # O(degree of node)
            if neighbor not in visited:     # O(1) — set lookup
                visited.add(neighbor)       # O(1) — mark visited
                queue.append(neighbor)      # O(1) — enqueue

    return result

def dfs_recursive(graph: dict, start: str,
                  visited: set | None = None) -> list[str]:
    """
    DFS on a graph — recursive version.

    Explores as deep as possible before backtracking.
    Uses the CALL STACK as an implicit stack.

    Time: O(V + E)
    Space: O(V) — visited set + recursion stack depth (up to V for linear graph)
    """
    if visited is None:
        visited = set()

    visited.add(start)      # Mark visited before diving deeper
    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: dict, start: str) -> list[str]:
    """
    DFS on a graph — iterative version with explicit stack.

    Time: O(V + E)
    Space: O(V)
    """
    visited = set()
    stack = [start]     # DFS uses a STACK — LIFO order
    result = []

    while stack:
        node = stack.pop()  # O(1) — list pop from end

        if node in visited:
            continue
        visited.add(node)
        result.append(node)

        # Push neighbors onto stack
        # Note: order may differ from recursive DFS (reversed neighbor order)
        for neighbor in graph[node]:
            if neighbor not in visited:
                stack.append(neighbor)

    return result