Graphs can feel intimidating because they aren't linear like a List or hierarchical like a Tree. But really, a graph is just a collection of "things" and the "connections" between them. To make this concrete, let's build a tiny social network. We've got users, and some of them are friends. Our goal is to figure out if two people are connected and, more importantly, how to traverse that network.

Mapping out the connections

I usually start by wondering how to actually store this in Java. I could use a 2D array (an adjacency matrix), but that's a memory nightmare if we have 10,000 users and only a few friendships each. I'll go with an adjacency list instead. A Map where the key is the person and the value is a list of their friends is the most flexible way to do this.

Map<String, List<String>> network = new HashMap<>();
// Let's add some data
network.put("Alice", new ArrayList<>(List.of("Bob", "Charlie")));
network.put("Bob", new ArrayList<>(List.of("Alice", "David")));
network.put("Charlie", new ArrayList<>(List.of("Alice", "Eve")));
network.put("David", new ArrayList<>(List.of("Bob")));
network.put("Eve", new ArrayList<>(List.of("Charlie")));

Simple enough. Now, let's say I want to see if Alice can eventually reach Eve through some chain of friends. My first instinct is to just write a recursive function that jumps from friend to friend. This is Depth-First Search (DFS).

The recursive trap

Here is my first attempt at a canReach method. I'll just pick a friend and dive deep into their friendship circle:

boolean canReach(String start, String target, Map<String, List<String>> network) {
    if (start.equals(target)) return true;
    for (String friend : network.getOrDefault(start, new ArrayList<>())) {
        if (canReach(friend, target, network)) return true;
    }
    return false;
}

If I run this with the data above, I'm going to hit a StackOverflowError almost immediately. Why? Look at Alice and Bob. Alice is friends with Bob, and Bob is friends with Alice. The code goes Alice → Bob → Alice → Bob... and it never stops. This is the classic "cycle" problem in graphs. We need a way to remember where we've already been.

Adding a memory to the search

To fix this, I'll pass along a Set to keep track of visited nodes. If I've already checked a person, I'll just skip them. This is the "standard" way to implement DFS.

boolean canReach(String current, String target, Map<String, List<String>> network, Set<String> visited) {
    if (current.equals(target)) return true;
    visited.add(current);

    for (String friend : network.getOrDefault(current, new ArrayList<>())) {
        if (!visited.contains(friend)) {
            if (canReach(friend, target, network, visited)) return true;
        }
    }
    return false;
}

Now it works. DFS is great for seeing if a path exists, but it's terrible for finding the shortest path. Because it dives deep, it might find a path that is 10 people long when there was actually a direct connection just two people away.

Switching gears to Breadth-First Search

If I want the shortest path (the "degrees of separation"), I need to explore the network in ripples. First, check all immediate friends. Then, check all friends-of-friends. This is Breadth-First Search (BFS). Instead of recursion (which uses a stack), I'll use a Queue.

I'll try to implement this by popping a person off the queue, marking them visited, and adding all their unvisited friends to the end of the line.

boolean shortestPathExists(String start, String target, Map<String, List<String>> network) {
    Queue<String> queue = new LinkedList<>();
    Set<String> visited = new HashSet<>();

    queue.add(start);
    visited.add(start);

    while (!queue.isEmpty()) {
        String current = queue.poll();
        if (current.equals(target)) return true;

        for (String friend : network.getOrDefault(current, new ArrayList<>())) {
            if (!visited.contains(friend)) {
                visited.add(friend);
                queue.add(friend);
            }
        }
    }
    return false;
}

Notice the subtle difference: in BFS, I mark the node as visited before putting it in the queue. If I waited until I polled it, I might add the same person to the queue multiple times from different friends, which is inefficient.

So, here's the takeaway: use DFS (recursion/stack) when you need to explore every nook and cranny or check for connectivity. Use BFS (queue) when you need the shortest path or are dealing with "levels" of distance.

📋 Practical Task

Exercise: Degrees of Separation Tracker

You are building a feature for a professional networking site. Instead of just returning a boolean, you need to find the actual number of "hops" between two people.

Your Task: Modify the BFS implementation provided in the lesson. Create a method int getDistance(String start, String target, Map<String, List<String>> network).

• If the start and target are the same person, return 0.
• If they are direct friends, return 1.
• If there is no path between them, return -1.

Hint: You can't just use a simple Queue of Strings anymore. You might need a way to store the distance along with the person (perhaps a small helper class or a Map to track distances from the start node).