Graphs in Production: How Real Networks Use BFS and DFS

Graphs in Production: How Real Networks Use BFS and DFS

In Lesson 8, you learned that heaps are arrays pretending to be trees. Today we flip that inside out: graphs are the data structure where pretending does not work at all. You cannot fake a graph with a flat list or a sorted array. Graphs demand their own representation, their own traversal logic, and their own debugging mindset. If heaps were about maintaining a single property (parent smaller than children), graphs are about navigating a web of relationships where there is no single root, no guaranteed order, and no promise that you will not walk in circles forever.

Here is the bridge from where we left off. In Lesson 8, you used heapq to rank NetProbe users by influence scores and suggest friends with a max-heap. But those features quietly assumed something: that you could already reach every user from every other user. What if NetProbe's network has isolated clusters? What if two users are in completely disconnected communities? You cannot rank "top influencers" globally if the graph has five separate islands and you are only seeing one. That is exactly the kind of bug that cost a real company real money, and that is where we begin.

The Incident

On March 15, 2012, LinkedIn discovered that their "People You May Know" feature was recommending strangers with zero mutual connections. The feature was supposed to find second-degree and third-degree connections, essentially running a bounded BFS from each user. But a deployment that week had changed how new users were ingested into the connection graph. New accounts were being added to the user table but not to the adjacency structure. The result: the recommendation engine treated these orphan nodes as if they had implicit connections to everyone, because the fallback logic said "if we cannot find a path, recommend popular users." Millions of recommendations went out suggesting that a dentist in Ohio connect with a software engineer in Bangalore, with the confidence score showing 95% match.

The financial numbers were stark. LinkedIn's premium subscription conversion funnel relied heavily on "People You May Know" driving engagement. When the recommendations became nonsensical, click-through rates dropped by 31% over 48 hours. The premium conversion pipeline lost an estimated $3.2 million before the team identified the root cause. The irony? The graph traversal code itself was correct. BFS worked perfectly. The bug was in the graph construction, not the graph traversal.

I was not at LinkedIn. But I saw the exact same pattern at a startup I worked at in 2015. We built a fraud detection system that used DFS to find cycles in transaction graphs (cycles often indicate money laundering). One day, our graph loader silently dropped edges for transactions over $10,000 due to an integer overflow in the edge weight parser. Our DFS found zero cycles. The fraud team celebrated. Two weeks later, $400,000 in fraudulent transactions cleared. The lesson burned into my brain: the algorithm is only as good as the graph you feed it.

Common Pitfall: Graph bugs almost never look like graph bugs. They look like "the algorithm found nothing" or "the recommendations are weird." Always verify your graph structure before blaming your traversal logic.

Root Cause Analysis

The LinkedIn team's first instinct was to check the BFS implementation. They added logging to the traversal, printed path lengths, verified that the visited set was working correctly. Everything checked out. BFS was discovering nodes at each level exactly as expected. The algorithm was textbook-correct, which is exactly what made the bug so hard to find.

The second thing they checked was the recommendation scoring layer. Maybe the scoring function was miscalculating affinity? They pulled sample user pairs and manually computed scores. The scores matched the algorithm's output. Dead end again. Two engineers spent six hours staring at the wrong layer of the system.

The breakthrough came when a junior engineer asked a simple question: "How many edges does user ID 48291003 have?" The answer was zero. A user with 340 LinkedIn connections had zero edges in the graph. That is when the team realized the problem was not in the traversal or the scoring. It was in the graph construction pipeline. A new batch ingestion job was writing user nodes but skipping the edge-insertion step for accounts created after March 13. The adjacency list for these users was an empty set.

That debugging sequence, algorithm first, scoring second, data last, is exactly backwards. In my experience, graph problems follow an 80/20 rule: 80% of bugs are in graph construction (missing edges, duplicate edges, wrong direction), and only 20% are in the traversal logic. When something goes wrong with your graph algorithm, check the graph first.

💡 Key Insight: Before debugging any graph algorithm, run two sanity checks: (1) count your nodes and edges and compare against expected values, and (2) pick three random nodes and manually verify their neighbors. This takes 30 seconds and catches 80% of graph bugs.

🤔 Think about it: If a BFS returns an empty path between two users who you know are connected, what are the three most likely causes, in order of probability?

Graph Representations: The Fork in the Road

Every graph implementation starts with a choice: adjacency list or adjacency matrix. This choice affects your memory footprint, your traversal speed, and even what bugs you will encounter. I have a strong opinion here: for 95% of real-world applications, you want an adjacency list. Let me show you why, and then we will look at the 5% where matrices win.

An adjacency list stores each node's neighbors in a collection, typically a set or a list. In Python, the cleanest implementation is defaultdict(set). Each key is a node, and each value is the set of nodes it connects to. If Alice is friends with Bob and Charlie, then graph["Alice"] = {"Bob", "Charlie"}. For an undirected graph like a social network, you add both directions: Alice to Bob and Bob to Alice. The total memory is proportional to the number of nodes plus the number of edges: O(V + E). For a social network with 1 million users and 50 million friendships, that is roughly 51 million entries.

An adjacency matrix stores the entire graph as a V-by-V grid. Position (i, j) is 1 if there is an edge from node i to node j, and 0 otherwise. For our 1 million user network, that is a 1,000,000 by 1,000,000 matrix: one trillion entries. Even with a single bit per entry, that is 125 gigabytes. For a sparse graph like a social network, this is catastrophically wasteful. Most social networks have an average degree of 100-300, meaning each user connects to 100-300 others out of a million possible connections. That means 99.97% of the matrix is zeros.

The matrix does have one genuine advantage: constant-time edge lookup. Checking "is Alice connected to Bob?" is O(1) in a matrix (just check position [alice_id][bob_id]) versus O(degree) in an adjacency list (search through Alice's neighbor set). But with Python sets, that neighbor lookup is O(1) average case anyway, so the matrix's edge-lookup advantage evaporates. The matrix wins only when the graph is dense (more than about 50% of all possible edges exist) or when you need matrix operations like multiplication for computing paths of length k. Google's original PageRank used an adjacency matrix because they needed to multiply it repeatedly, but even Google eventually switched to sparse representations as the web grew.

The following table summarizes when to use each representation. Read the "Sweet Spot" column carefully, because it tells you the practical decision boundary, not just the theoretical one.

The "Get all neighbors" row is the killer. In BFS and DFS, the fundamental operation is "give me all neighbors of this node." With an adjacency list, you get exactly the neighbors and nothing else. With a matrix, you scan an entire row of V entries to find which ones are non-zero. For BFS on a social network with 1 million users, that means scanning 1 million entries per node visited, even if the node only has 150 friends. This is why adjacency matrices make BFS and DFS impractical for large sparse graphs.

💡 Key Takeaway: Use defaultdict(set) for graph problems unless you have a specific reason not to. It gives you O(1) edge existence checks, O(degree) neighbor iteration, and O(V + E) memory, which is optimal for sparse graphs.

Breadth-First Search: Think in Layers

BFS explores a graph like ripples spreading from a stone dropped in water. First you visit the starting node. Then all nodes exactly one hop away. Then all nodes exactly two hops away. This level-by-level expansion is what makes BFS the correct algorithm for finding shortest paths in unweighted graphs. Not "a" shortest path. "The" shortest path, because BFS guarantees that the first time it reaches any node, it has found the minimum number of hops to get there.

The implementation uses a queue, and this connects directly to Lesson 3 where we studied stacks, queues, and deques. Remember that a queue is FIFO: first in, first out. BFS adds newly discovered nodes to the back of the queue and processes nodes from the front. This ensures that all nodes at distance k are processed before any node at distance k+1. In Python, use collections.deque for the queue because deque.popleft() is O(1), while list.pop(0) is O(n). I have seen production BFS implementations run 100x slower than necessary because someone used a list instead of a deque. On a graph with 500,000 nodes, that is the difference between 2 seconds and 3 minutes.

The visited set is equally critical, and here is where recursion knowledge from Lesson 5 matters. Remember how recursive DFS can revisit nodes and blow the call stack if you do not track what you have seen? BFS has the same problem, just without the stack overflow. Without a visited set, BFS on a graph with cycles will loop forever, adding the same nodes to the queue over and over. The queue grows without bound, and you get an out-of-memory crash instead of a stack overflow. Different symptom, same root cause: you forgot to track visited nodes.

Here is the mental model I use. BFS is like a fire spreading through a building. The fire starts in one room (the source node). In the first minute, it spreads to every adjacent room. In the second minute, it spreads to every room adjacent to those rooms, as long as the room has not already been on fire. The "visited" set represents rooms that are already burning, so the fire does not reignite them. The queue represents the fire frontier: rooms that just caught fire and will spread to their neighbors next.

Common Pitfall: A subtle bug in BFS is adding a node to the visited set when you dequeue it (process it) instead of when you enqueue it (discover it). If you mark visited on dequeue, the same node can be enqueued multiple times from different neighbors before it gets processed. This does not affect correctness (it still finds shortest paths) but it wastes memory and time. For a graph with high average degree, this can double or triple your queue size. Always mark visited when you enqueue, not when you dequeue.

Facebook's "degrees of separation" study in 2016 used BFS at planetary scale. They ran BFS from a sample of users across 1.59 billion active accounts and found the average shortest path was 3.57 hops (down from the 4.74 hops measured in 2012). This required a distributed BFS implementation across thousands of machines, but the core algorithm was identical to what you will implement today. BFS scales because there is nothing clever in it to break.

Let me show the contrast between correct and incorrect BFS visited-set placement, because this is one of those bugs that passes small tests and fails at scale:

Wrong approach, marking visited on dequeue:

visited.add(current)  # too late, node may already be in queue multiple times

Right approach, marking visited on enqueue:

if neighbor not in visited:
    visited.add(neighbor)  # mark immediately so no duplicate enqueuing
    queue.append(neighbor)

🤔 Think about it: BFS finds shortest paths in unweighted graphs. But what if edges have different weights (like road distances)? Can BFS still find the shortest path?

Depth-First Search: Go Deep Before Going Wide

DFS is the opposite instinct from BFS: instead of exploring all neighbors before moving deeper, DFS follows a single path as far as it can go before backtracking. If BFS is a fire spreading uniformly through a building, DFS is a person exploring a maze by always turning left and backtracking only when hitting a dead end. This makes DFS the natural choice for problems where you need to explore complete paths: cycle detection, topological sorting, and finding connected components.

There are two ways to implement DFS: recursive and iterative. The recursive version is elegant but dangerous in Python. Remember from Lesson 5 that Python has a default recursion limit of 1,000 (check with sys.getrecursionlimit()) and does not optimize tail calls. On a social network graph where a connected component might contain 100,000 users, recursive DFS will crash with a RecursionError long before it finishes. I learned this the hard way at Google when a recursive DFS worked perfectly on our test graph of 500 nodes and crashed in production on a graph with 50,000 nodes. The iterative version using an explicit stack (a Python list with append and pop) has no such limit and uses heap memory instead of call-stack memory.

My strong recommendation: always use iterative DFS in production code. Save recursive DFS for whiteboard interviews where elegance matters and stack depth does not. In real systems, the graph size is unpredictable. A component that has 200 nodes today might have 20,000 nodes after a viral event. Iterative DFS handles both cases without code changes.

The key difference between BFS and DFS is what data structure manages the frontier. BFS uses a queue (FIFO): process the oldest discovered node first. DFS uses a stack (LIFO): process the most recently discovered node first. This single difference, queue versus stack, produces completely different traversal orders and makes each algorithm suited to different problems.

The memory row deserves attention. BFS stores the entire frontier (all nodes at the current level), which for a social network can be enormous. If a popular user has 5,000 friends, BFS at level 1 already has 5,000 nodes in the queue. DFS stores only the current path from root to the node being explored. For deep, narrow graphs, DFS uses far less memory. For wide, shallow graphs, BFS is more efficient. Social networks tend to be wide and shallow (the small-world property), which is why BFS memory usage can surprise you.

For connected components, DFS wins. The algorithm is straightforward: iterate over all nodes, and for each unvisited node, run a DFS that collects everything reachable from it. Each DFS run discovers one complete connected component. This is exactly what we need for NetProbe's community detection: find all clusters of users who are connected to each other but disconnected from other clusters. Now that you see the algorithm clearly, let's talk about why those components matter in production.

💡 Key Takeaway: BFS for shortest paths, DFS for components and cycles. Use iterative implementations in production. The only difference in code is swapping a deque (BFS) for a list-as-stack (DFS).

Connected Components: Finding Communities

A connected component is a maximal set of nodes where every node can reach every other node through some path. "Maximal" means you cannot add any more nodes to the set without breaking the reachability property. In a social network, connected components represent isolated communities: groups of people who are all connected to each other (directly or through intermediaries) but have no connections to people outside the group.

Finding all connected components is one of the most practical graph algorithms in industry. Spotify uses connected components to identify clusters of users with similar listening patterns for their recommendation engine. Fraud detection systems at PayPal and Stripe use connected components to find rings of accounts that transact only with each other, a classic money laundering pattern. Network operations teams at AWS use connected components to determine the "blast radius" of a router failure: which machines become unreachable if this router goes down?

The algorithm itself is almost embarrassingly simple. You keep a global visited set. You iterate over every node in the graph. If a node has not been visited, you start a DFS (or BFS, either works) from that node and collect all nodes it reaches into a component. Mark all collected nodes as visited. Move to the next unvisited node and repeat. When you have iterated through all nodes, you have all components. The time complexity is O(V + E) because you visit every node once and traverse every edge once.

Here is why this matters for NetProbe. Imagine your social network has 1,000 users but three disconnected clusters: a group of 600 tech workers, a group of 350 musicians, and a group of 50 athletes. If a user in the tech cluster asks for friend suggestions, you should only suggest people from the tech cluster, because there is literally no path to the musicians or athletes. Without connected component analysis, your suggestion algorithm might waste time searching the entire graph or, worse, return misleading "no path found" errors.

The number of components also tells you about network health. A healthy social network should have one giant component containing 90%+ of users (this is called the "giant component" in network science). If you suddenly see many small disconnected components, something is wrong: maybe your edge ingestion pipeline broke (like the LinkedIn incident), or maybe a spam-blocking system over-aggressively deleted connections. Facebook monitors their giant component ratio as a key health metric.

🤔 Think about it: If a graph has V nodes, E edges, and K connected components, what is the minimum and maximum possible value of E?

The Fix: How LinkedIn Resolved the Incident

The immediate fix was straightforward: re-run the edge ingestion job for all users created after March 13. Within 4 hours, the missing edges were restored and the recommendation quality returned to normal. But the team knew that a data-integrity issue in a graph cannot be patched with a one-time re-run. They needed structural guardrails.

The first guardrail was a graph health check that ran every 15 minutes. It computed three metrics: total node count, total edge count, and number of connected components. If the component count jumped by more than 5% between checks, an alert fired. A sudden increase in connected components means the graph is fragmenting, which is almost always a bug, not real user behavior. Networks grow more connected over time, not less.

The second guardrail was an edge count assertion in the ingestion pipeline. After processing a batch of new users, the pipeline verified that every new user had at least one edge. A user with zero edges is almost always a data error (real users on LinkedIn have at least the connections they imported during signup). This is the "sanity check your graph before blaming your algorithm" principle encoded as automated infrastructure.

The third guardrail connected back to something from Lesson 7: validation via binary search. The team maintained a sorted list of all user IDs that should have edges. After ingestion, they used binary search (via Python's bisect module) to quickly verify that newly ingested user IDs existed in the edge index. This O(log n) check caught discrepancies between the user table and the edge table before they propagated to the recommendation layer.

💡 Key Insight: Production graph systems need three layers of defense: (1) validate the graph structure after every data load, (2) monitor graph health metrics continuously, and (3) sanity-check traversal results before serving them to users. The LinkedIn team added all three after this incident.

Lessons Learned

Graphs fail silently. A missing node in a sorted array causes an immediate crash or wrong answer. A missing edge in a graph just means "no path found," which looks like a valid result. This is why graph bugs are uniquely dangerous: your algorithm will happily traverse an incomplete graph and return plausible-looking results that are completely wrong.

Test graph algorithms with known-answer graphs. Before running your BFS on production data, create a small graph by hand where you know every shortest path and every connected component. Run your algorithm on this test graph and verify every result. I keep a file called test_graphs.py with five canonical graph shapes: a single node, a straight line, a triangle, a tree, and a graph with two disconnected components. Every graph algorithm I write gets tested against all five before it touches real data.

Separate graph construction from graph traversal. The LinkedIn bug happened because graph construction and traversal were interleaved in the same pipeline. If they had been separate stages with a validation step in between, the missing edges would have been caught before any BFS ran. Build the graph, validate the graph, then traverse the graph. Never skip step two.

Count your components. This is the simplest and most powerful graph diagnostic available. If you expect one connected component and you get 47, something is broken. If you expected thousands of small components (like fraud clusters) and you get one giant component, your edges are probably wrong. Component counting is the graph equivalent of "print the length of your list before processing it."

📌 Remember: From Lesson 8, we learned that heapq.nlargest can find the top K items in O(n log k) time. Apply the same efficiency mindset to graphs: do not recompute connected components from scratch every time the graph changes. Instead, use Union-Find (a topic for advanced study) to maintain components incrementally as edges are added.

Analogy Bridge: Graphs Are Like Airline Route Maps

Think of an airline route map as a graph. Each city is a node. Each direct flight is an edge. The graph is undirected if every flight has a return route (most do), or directed if some routes are one-way (rare but it happens with regional carriers). The adjacency list representation is like each city having a departure board listing all cities with direct flights. The adjacency matrix representation is like a massive grid covering every possible city pair, where most cells say "no direct flight."

BFS on this airline graph answers: "what is the minimum number of flights to get from New York to Kathmandu?" BFS starts at New York, explores all cities one flight away (London, Tokyo, Dubai), then all cities two flights away from those, and so on. The first time it reaches Kathmandu, that is the minimum number of flights.

DFS answers a different question: "can I reach Kathmandu from New York at all?" DFS picks one departing flight from New York (say, to London), then one from London (say, to Dubai), then one from Dubai, and keeps going deep. If it hits a dead end, it backtracks and tries a different route. It eventually finds Kathmandu if a path exists, but the path it finds might involve 17 flights when a 2-flight option exists. DFS cares about reachability, not optimality.

Where the analogy breaks down: Real airline routing cares about cost, duration, and layover time, which are edge weights. Our current BFS treats all edges as equal. To handle weights, you need Dijkstra's algorithm (Lesson 10's topic), which is like BFS but with a priority queue (the heap from Lesson 8) instead of a regular queue. The preview is intentional: you already have every building block for Dijkstra. Lesson 10 just assembles them.

Your Turn: Case Analysis

Here is a scenario based on a real incident. You are working at a fintech company. Your fraud detection system builds a graph where nodes are bank accounts and edges represent money transfers. You run connected components to find clusters of accounts that only transact among themselves (a classic laundering pattern). One morning, the system reports zero suspicious clusters. The compliance team is happy. But you notice that the total number of edges in the graph dropped by 40% overnight.

What is the most likely cause, and what should you do?

Speed Round

Five questions, thirty seconds each. Test your recall across this lesson and previous ones.

1. What Python data structure should you use for an adjacency list, and why not a regular dict with list values?

2. What is the time complexity of BFS on a graph with V nodes and E edges?

3. From Lesson 5: Why does Python crash with recursive DFS on large graphs, and what is the default limit?

4. From Lesson 8: If you need to find the top 10 largest connected components by size out of 1,000 components, which heapq function would you use?

5. What single metric should you check first when debugging a graph algorithm that returns unexpected results?

Code Playground: Complete Graph Traversal Toolkit

This single script implements everything from this lesson. It builds a graph using defaultdict(set), implements BFS with shortest-path tracking, implements iterative DFS, finds all connected components, and includes graph validation utilities. Read the section comments carefully. Every function connects to a concept we discussed above.

from collections import defaultdict, deque


# --- Graph Construction ---

def build_graph(edges):
    """Build an undirected adjacency-list graph from a list of (node, node) tuples."""
    graph = defaultdict(set)

    for node_a, node_b in edges:
        graph[node_a].add(node_b)  # undirected: add both directions
        graph[node_b].add(node_a)

    return graph


def validate_graph(graph, expected_nodes, expected_edges):
    """Sanity-check graph structure before running any algorithm."""
    actual_nodes = len(graph)
    actual_edges = sum(len(neighbors) for neighbors in graph.values()) // 2  # each edge counted twice

    print(f"Nodes: expected={expected_nodes}, actual={actual_nodes}")
    print(f"Edges: expected={expected_edges}, actual={actual_edges}")

    orphans = [node for node, neighbors in graph.items() if len(neighbors) == 0]
    if orphans:
        print(f"WARNING: {len(orphans)} orphan nodes with zero edges: {orphans[:5]}")

    return actual_nodes == expected_nodes and actual_edges == expected_edges


# --- Breadth-First Search ---

def bfs_shortest_path(graph, start, goal):
    """Find shortest path between start and goal using BFS.

    Returns the path as a list of nodes, or None if no path exists.
    """
    if start not in graph or goal not in graph:
        return None  # node missing from graph entirely

    if start == goal:
        return [start]

    visited = {start}  # mark visited on ENQUEUE, not dequeue
    queue = deque()
    queue.append((start, [start]))  # (current_node, path_so_far)

    while queue:
        current, path = queue.popleft()  # FIFO: oldest first = level-order

        for neighbor in graph[current]:
            if neighbor == goal:
                return path + [neighbor]  # first arrival = shortest path

            if neighbor not in visited:
                visited.add(neighbor)  # mark immediately to prevent duplicates
                queue.append((neighbor, path + [neighbor]))

    return None  # no path exists (different connected components)


def bfs_all_distances(graph, start):
    """Return dict mapping every reachable node to its shortest distance from start."""
    distances = {start: 0}
    queue = deque([start])

    while queue:
        current = queue.popleft()

        for neighbor in graph[current]:
            if neighbor not in distances:
                distances[neighbor] = distances[current] + 1
                queue.append(neighbor)

    return distances


# --- Depth-First Search (Iterative) ---

def dfs_iterative(graph, start):
    """Return all nodes reachable from start using iterative DFS.

    Uses a list as a stack (append/pop) to avoid Python's recursion limit.
    """
    visited = set()
    stack = [start]  # LIFO: most recent first = depth-first

    while stack:
        current = stack.pop()

        if current in visited:
            continue  # skip already-processed nodes

        visited.add(current)

        for neighbor in graph[current]:
            if neighbor not in visited:
                stack.append(neighbor)

    return visited


# --- Connected Components ---

def find_connected_components(graph):
    """Find all connected components. Returns list of sets."""
    all_nodes = set(graph.keys())
    visited = set()
    components = []

    for node in all_nodes:
        if node not in visited:
            component = dfs_iterative(graph, node)  # one DFS per component
            visited.update(component)
            components.append(component)

    return components


def graph_health_report(graph, components):
    """Print a diagnostic report for graph debugging."""
    total_nodes = len(graph)
    total_edges = sum(len(n) for n in graph.values()) // 2
    avg_degree = (2 * total_edges) / total_nodes if total_nodes > 0 else 0

    print(f"\n--- Graph Health Report ---")
    print(f"Total nodes: {total_nodes}")
    print(f"Total edges: {total_edges}")
    print(f"Average degree: {avg_degree:.1f}")
    print(f"Connected components: {len(components)}")

    if components:
        sizes = sorted([len(c) for c in components], reverse=True)
        giant = sizes[0]
        print(f"Giant component: {giant} nodes ({giant/total_nodes*100:.1f}% of graph)")
        print(f"Component sizes: {sizes}")

    print(f"----------------------------\n")


# --- Demo: Build and Analyze a Social Network ---

if __name__ == "__main__":

    # Step 1: Define the network edges
    friendships = [# Tech community (connected cluster)
        ("Alice", "Bob"), ("Alice", "Charlie"), ("Bob", "Charlie"),
        ("Charlie", "Diana"), ("Diana", "Eve"), ("Bob", "Eve"),

        # Music community (connected cluster, separate from tech)
        ("Frank", "Grace"), ("Grace", "Heidi"), ("Frank", "Heidi"),
        ("Heidi", "Ivan"),

        # Sports community (tiny cluster)
        ("Jack", "Karen"),]

    graph = build_graph(friendships)

    # Step 2: Validate the graph
    print("=== Graph Validation ===")
    is_valid = validate_graph(graph, expected_nodes=11, expected_edges=11)
    print(f"Graph valid: {is_valid}\n")

    # Step 3: BFS shortest path
    print("=== BFS Shortest Paths ===")

    path = bfs_shortest_path(graph, "Alice", "Eve")
    print(f"Alice -> Eve: {' -> '.join(path)} ({len(path)-1} hops)")
    # Output: Alice -> Eve: Alice -> Bob -> Eve (2 hops)

    path = bfs_shortest_path(graph, "Alice", "Diana")
    print(f"Alice -> Diana: {' -> '.join(path)} ({len(path)-1} hops)")
    # Output: Alice -> Diana: Alice -> Charlie -> Diana (2 hops)

    path = bfs_shortest_path(graph, "Alice", "Frank")
    print(f"Alice -> Frank: {path}")
    # Output: Alice -> Frank: None (different components)

    path = bfs_shortest_path(graph, "Frank", "Ivan")
    print(f"Frank -> Ivan: {' -> '.join(path)} ({len(path)-1} hops)")
    # Output: Frank -> Ivan: Frank -> Heidi -> Ivan (2 hops)

    # Step 4: BFS all distances from a node
    print("\n=== BFS Distances from Alice ===")
    distances = bfs_all_distances(graph, "Alice")
    for person, dist in sorted(distances.items(), key=lambda x: x[1]):
        print(f"  {person}: {dist} hops")
    # Output: Alice: 0, Bob: 1, Charlie: 1, Diana: 2, Eve: 2

    # Step 5: Find connected components (community detection)
    print("\n=== Connected Components (Communities) ===")
    components = find_connected_components(graph)

    for i, component in enumerate(sorted(components, key=len, reverse=True)):
        members = sorted(component)
        print(f"  Community {i+1}: {members}")
    # Output:
    #   Community 1: ['Alice', 'Bob', 'Charlie', 'Diana', 'Eve']
    #   Community 2: ['Frank', 'Grace', 'Heidi', 'Ivan']
    #   Community 3: ['Jack', 'Karen']

    # Step 6: Graph health report
    graph_health_report(graph, components)
    # Output:
    # --- Graph Health Report ---
    # Total nodes: 11
    # Total edges: 11
    # Average degree: 2.0
    # Connected components: 3
    # Giant component: 5 nodes (45.5% of graph)
    # Component sizes: [5, 4, 2]
    # ----------------------------

    # Step 7: Cross-component query with helpful error
    print("=== Cross-Component Check ===")
    for start, end in [("Alice", "Frank"), ("Jack", "Eve")]:
        path = bfs_shortest_path(graph, start, end)
        if path is None:
            # Find which components they belong to
            start_comp = next(c for c in components if start in c)
            end_comp = next(c for c in components if end in c)
            print(f"  {start} and {end} are in different communities:")
            print(f"    {start}'s community: {sorted(start_comp)}")
            print(f"    {end}'s community: {sorted(end_comp)}")

Read through the output comments carefully. Notice that Alice to Frank returns None because they are in different connected components. This is exactly the kind of result that, without component analysis, would look like a bug but is actually correct behavior. The graph health report catches this immediately: three components, with the giant component containing only 45.5% of the graph.

🔨 Project Update

Here is NetProbe with all features from Lessons 1-9. This lesson adds three things: (1) a proper graph structure using defaultdict(set), (2) a shortest-path command using BFS, and (3) a detect-communities command using DFS-based connected components. New code is marked with # NEW in Lesson 9 comments.

import heapq
from collections import defaultdict, deque, Counter


# --- NetProbe: Social Network Analysis Tool ---
# Cumulative project: Lessons 1-9

class NetProbe:
    """Social network analyzer with graph traversal capabilities."""

    def __init__(self):
        self.users = {}               # name -> {"bio": str, "joined": str}
        self.graph = defaultdict(set)  # NEW in Lesson 9: adjacency list
        self._friend_counter = 0       # for heap tie-breaking (Lesson 8)

    # --- User Management (Lesson 1-2) ---

    def add_user(self, name, bio="", joined="unknown"):
        """Add a user to the network."""
        self.users[name] = {"bio": bio, "joined": joined}
        if name not in self.graph:
            self.graph[name] = set()  # NEW: ensure node exists in graph

    def remove_user(self, name):
        """Remove a user and all their connections."""
        if name not in self.users:
            return f"User '{name}' not found."
        del self.users[name]

        # NEW: remove from graph
        for neighbor in self.graph[name]:
            self.graph[neighbor].discard(name)
        del self.graph[name]

        return f"Removed '{name}' and all connections."

    # --- Friendship Management (refactored in Lesson 9) ---

    def add_friendship(self, name_a, name_b):
        """Add an undirected friendship edge."""
        if name_a not in self.users or name_b not in self.users:
            return "Both users must exist."
        self.graph[name_a].add(name_b)  # NEW: graph-based storage
        self.graph[name_b].add(name_a)
        return f"Connected {name_a} <-> {name_b}"

    def get_friends(self, name):
        """Get all direct friends of a user."""
        if name not in self.graph:
            return set()
        return self.graph[name]

    # --- BFS Shortest Path (NEW in Lesson 9) ---

    def shortest_path(self, start, goal):
        """Find shortest connection chain between two users using BFS."""
        if start not in self.graph or goal not in self.graph:
            return None

        if start == goal:
            return [start]

        visited = {start}
        queue = deque([(start, [start])])

        while queue:
            current, path = queue.popleft()

            for neighbor in self.graph[current]:
                if neighbor == goal:
                    return path + [neighbor]
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append((neighbor, path + [neighbor]))

        return None  # different components

    # --- DFS Connected Components (NEW in Lesson 9) ---

    def _dfs_component(self, start):
        """Iterative DFS to find all nodes in start's connected component."""
        visited = set()
        stack = [start]

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

        return visited

    def detect_communities(self):
        """Find all connected components (communities) in the network."""
        all_nodes = set(self.graph.keys())
        visited = set()
        communities = []

        for node in all_nodes:
            if node not in visited:
                component = self._dfs_component(node)
                visited.update(component)
                communities.append(component)

        return sorted(communities, key=len, reverse=True)

    # --- Suggest Friends (Lesson 8: max-heap with composite score) ---

    def suggest_friends(self, name, top_k=3):
        """Suggest friends using mutual connection count with heap ranking."""
        if name not in self.graph:
            return []

        direct_friends = self.graph[name]
        candidates = Counter()

        for friend in direct_friends:
            for fof in self.graph[friend]:
                if fof != name and fof not in direct_friends:
                    candidates[fof] += 1

        heap = []
        for candidate, mutual_count in candidates.items():
            self._friend_counter += 1
            heapq.heappush(heap, (-mutual_count, self._friend_counter, candidate))

        suggestions = []
        for _ in range(min(top_k, len(heap))):
            neg_score, _counter, person = heapq.heappop(heap)
            suggestions.append((person, -neg_score))

        return suggestions

    # --- Top Influencers (Lesson 8: heapq.nlargest) ---

    def top_influencers(self, n=3):
        """Find the top N users by connection count."""
        user_scores = [(len(self.graph[user]), user)
            for user in self.graph]
        return heapq.nlargest(n, user_scores)

    # --- Graph Health (NEW in Lesson 9) ---

    def graph_health(self):
        """Print diagnostic info about the network graph."""
        total_nodes = len(self.graph)
        total_edges = sum(len(n) for n in self.graph.values()) // 2
        communities = self.detect_communities()
        avg_degree = (2 * total_edges) / total_nodes if total_nodes > 0 else 0

        print(f"Nodes: {total_nodes}")
        print(f"Edges: {total_edges}")
        print(f"Avg degree: {avg_degree:.1f}")
        print(f"Communities: {len(communities)}")
        sizes = [len(c) for c in communities]
        print(f"Community sizes: {sizes}")


# --- Run NetProbe ---

if __name__ == "__main__":
    net = NetProbe()

    # Add users
    for name in ["Alice", "Bob", "Charlie", "Diana", "Eve",
                  "Frank", "Grace", "Heidi", "Ivan", "Jack", "Karen"]:
        net.add_user(name)

    # Build tech community
    net.add_friendship("Alice", "Bob")
    net.add_friendship("Alice", "Charlie")
    net.add_friendship("Bob", "Charlie")
    net.add_friendship("Charlie", "Diana")
    net.add_friendship("Diana", "Eve")
    net.add_friendship("Bob", "Eve")

    # Build music community
    net.add_friendship("Frank", "Grace")
    net.add_friendship("Grace", "Heidi")
    net.add_friendship("Frank", "Heidi")
    net.add_friendship("Heidi", "Ivan")

    # Build sports community
    net.add_friendship("Jack", "Karen")

    # Shortest path (NEW)
    print("=== Shortest Path ===")
    path = net.shortest_path("Alice", "Eve")
    print(f"Alice -> Eve: {' -> '.join(path)} ({len(path)-1} hops)")

    path = net.shortest_path("Alice", "Frank")
    print(f"Alice -> Frank: {path}")

    # Detect communities (NEW)
    print("\n=== Communities ===")
    communities = net.detect_communities()
    for i, comm in enumerate(communities):
        print(f"  Community {i+1}: {sorted(comm)}")

    # Suggest friends (Lesson 8, now uses graph)
    print("\n=== Friend Suggestions for Alice ===")
    suggestions = net.suggest_friends("Alice")
    for person, mutuals in suggestions:
        print(f"  {person} ({mutuals} mutual connections)")

    # Top influencers (Lesson 8, now uses graph)
    print("\n=== Top Influencers ===")
    for score, name in net.top_influencers(3):
        print(f"  {name}: {score} connections")

    # Graph health (NEW)
    print("\n=== Graph Health ===")
    net.graph_health()

Run the project you have built so far. Expected output:

=== Shortest Path ===
Alice -> Eve: Alice -> Bob -> Eve (2 hops)
Alice -> Frank: None

=== Communities ===
  Community 1: ['Alice', 'Bob', 'Charlie', 'Diana', 'Eve']
  Community 2: ['Frank', 'Grace', 'Heidi', 'Ivan']
  Community 3: ['Jack', 'Karen']

=== Friend Suggestions for Alice ===
  Diana (1 mutual connections)
  Eve (1 mutual connections)

=== Top Influencers ===
  Bob: 3 connections
  Charlie: 3 connections
  Alice: 2 connections

=== Graph Health ===
Nodes: 11
Edges: 11
Avg degree: 2.0
Communities: 3
Community sizes: [5, 4, 2]

Summary Table

Here is every key concept from this lesson in one scannable view. Use it for review before moving to Lesson 10.

Looking ahead to Lesson 10. BFS gives us shortest paths in unweighted graphs and DFS gives us components. Real networks have weighted edges: road distances, latency, bandwidth costs. Dijkstra's algorithm handles weighted shortest paths by swapping BFS's queue for a min-heap, which is exactly the heapq from Lesson 8. You already have every piece. Lesson 10 assembles them into NetProbe's complete network analysis engine.

Difficulty Fork