Graphs: Matrix, Adjacency List, BFS, DFS, and Dijkstra

A tree has a strict rule: each node has exactly one parent and there are no cycles. That is enough for hierarchies, but falls short for almost everything else.

In a social network, if you are friends with Ana and Ana is friends with Luis, and Luis is also friends with you, who is whose parent? On a street map, which corner is the root? Neither question makes sense, because that is not a tree: it is a graph.

A graph is the most general structure of all. In fact, a tree is simply a graph with restrictions: connected, acyclic, and with a chosen root.

1. Vocabulary

Examples you already use every day:

2. The two ways to represent it

A graph is not stored “as it looks”. There are two standard representations, and choosing wrong is expensive.

In Java, the adjacency list is written with a Map, which you already know from the Java Collections and Generics (JCF) lesson:

public class Graph<V> {
    private final Map<V, List<V>> adjacency = new HashMap<>();

    public void addVertex(V v) {
        adjacency.putIfAbsent(v, new ArrayList<>());
    }

    // Undirected: the edge is added in both directions
    public void addEdge(V from, V to) {
        adjacency.computeIfAbsent(from, k -> new ArrayList<>()).add(to);
        adjacency.computeIfAbsent(to,   k -> new ArrayList<>()).add(from);
    }

    public List<V> neighbors(V v) {
        return adjacency.getOrDefault(v, List.of());
    }
}

Notice that computeIfAbsent and getOrDefault — the Map methods from the Java Collections and Generics (JCF) lesson — do all the heavy lifting. Without them you would need four extra if blocks.

3. BFS and DFS: the same algorithm with different memory

Traversing a graph has a problem trees did not: cycles. If A connects to B, B to C, and C back to A, a naive traversal loops forever.

The fix is a Set of visited vertices. And with that, the two classic traversals differ in exactly one thing: which structure holds the pending vertices.

// BFS — queue: first in, first out
public List<V> bfs(V start) {
    List<V> order = new ArrayList<>();
    Set<V> visited = new HashSet<>();
    Queue<V> pending = new ArrayDeque<>();

    visited.add(start);       // ← mark ON ENQUEUE, not on dequeue
    pending.offer(start);

    while (!pending.isEmpty()) {
        V current = pending.poll();
        order.add(current);

        for (V neighbor : neighbors(current)) {
            if (visited.add(neighbor)) {     // add returns false if already present
                pending.offer(neighbor);
            }
        }
    }
    return order;
}

// DFS — recursive: the JVM call stack serves as the stack
public List<V> dfs(V start) {
    List<V> order = new ArrayList<>();
    dfs(start, new HashSet<>(), order);
    return order;
}

private void dfs(V current, Set<V> visited, List<V> order) {
    if (!visited.add(current)) return;   // already visited: stop
    order.add(current);
    for (V neighbor : neighbors(current)) {
        dfs(neighbor, visited, order);
    }
}

Mark as visited on enqueue, not on dequeue. If you wait until you pull it off the queue, the same vertex can be enqueued several times before it is first processed. On a large graph that is not a detail: it multiplies the work and can exhaust memory.

4. Dijkstra: the cheapest path

BFS finds the path with the fewest edges. But when edges carry weight — kilometers, minutes, cost — the path with the fewest hops can be wildly expensive.

public Map<V, Integer> dijkstra(V source) {
    Map<V, Integer> distance = new HashMap<>();
    Set<V> visited = new HashSet<>();

    // The priority queue from Java Collections and Generics (JCF): always pulls the cheapest
    PriorityQueue<V> queue = new PriorityQueue<>(
        Comparator.comparingInt(v -> distance.getOrDefault(v, Integer.MAX_VALUE))
    );

    distance.put(source, 0);
    queue.offer(source);

    while (!queue.isEmpty()) {
        V current = queue.poll();
        if (!visited.add(current)) continue;   // already processed

        for (Edge<V> edge : edgesFrom(current)) {
            int candidate = distance.get(current) + edge.weight();
            // "Relax": if this route is cheaper, record it
            if (candidate < distance.getOrDefault(edge.to(), Integer.MAX_VALUE)) {
                distance.put(edge.to(), candidate);
                queue.offer(edge.to());
            }
        }
    }
    return distance;
}

Dijkstra does not work with negative weights. Its guarantee rests on a visited vertex’s distance being final; a negative weight breaks that. For that case there is Bellman-Ford.

5. Common mistakes

6. Guided hands-on exercise

Challenge: degrees of separation in a social network

Implement minimumHops(String from, String to) returning the minimum number of intermediaries between two people, plus shortestPath(...) returning the chain of people.

Think about why BFS is the only correct choice here, and why DFS would give the wrong answer.

import java.util.*;

public class SocialNetwork {

    private final Map<String, List<String>> friends = new HashMap<>();

    public void addFriendship(String a, String b) {
        // Undirected: friendship goes both ways
        friends.computeIfAbsent(a, k -> new ArrayList<>()).add(b);
        friends.computeIfAbsent(b, k -> new ArrayList<>()).add(a);
    }

    /**
     * BFS: returns the minimum number of hops, or -1 when unreachable.
     * DFS is NO good here: it would find *a* path, not the shortest one.
     */
    public int minimumHops(String from, String to) {
        if (!friends.containsKey(from) || !friends.containsKey(to)) return -1;
        if (from.equals(to)) return 0;

        Set<String> visited = new HashSet<>();
        Queue<String> queue = new ArrayDeque<>();

        visited.add(from);
        queue.offer(from);
        int hops = 0;

        while (!queue.isEmpty()) {
            int peopleAtThisLevel = queue.size();   // ← the key to counting levels
            hops++;

            for (int i = 0; i < peopleAtThisLevel; i++) {
                String current = queue.poll();

                for (String friend : friends.getOrDefault(current, List.of())) {
                    if (friend.equals(to)) return hops;
                    if (visited.add(friend)) {      // add returns false if present
                        queue.offer(friend);
                    }
                }
            }
        }
        return -1;   // walked everything reachable and never found them
    }

    /**
     * Same idea, but recording where each person was reached from
     * so the path can be reconstructed at the end.
     */
    public List<String> shortestPath(String from, String to) {
        if (!friends.containsKey(from) || !friends.containsKey(to)) return List.of();

        Map<String, String> cameFrom = new HashMap<>();
        Set<String> visited = new HashSet<>();
        Queue<String> queue = new ArrayDeque<>();

        visited.add(from);
        queue.offer(from);

        while (!queue.isEmpty()) {
            String current = queue.poll();

            if (current.equals(to)) {
                // Rebuild the path by walking backwards from the destination
                LinkedList<String> path = new LinkedList<>();
                for (String p = to; p != null; p = cameFrom.get(p)) {
                    path.addFirst(p);
                }
                return path;
            }

            for (String friend : friends.getOrDefault(current, List.of())) {
                if (visited.add(friend)) {
                    cameFrom.put(friend, current);   // remember the traversal parent
                    queue.offer(friend);
                }
            }
        }
        return List.of();
    }

    public static void main(String[] args) {
        SocialNetwork net = new SocialNetwork();
        net.addFriendship("Ana",   "Beto");
        net.addFriendship("Beto",  "Carla");
        net.addFriendship("Carla", "Diego");
        net.addFriendship("Ana",   "Elena");
        net.addFriendship("Elena", "Diego");
        net.addFriendship("Fabian","Gala");   // group disconnected from the rest

        System.out.println("Ana → Diego  : " + net.minimumHops("Ana", "Diego"));
        System.out.println("Path         : " + net.shortestPath("Ana", "Diego"));
        System.out.println("Ana → Fabian : " + net.minimumHops("Ana", "Fabian"));
        System.out.println("Ana → Ana    : " + net.minimumHops("Ana", "Ana"));
    }
}

Ana → Diego  : 2
Path         : [Ana, Elena, Diego]
Ana → Fabian : -1
Ana → Ana    : 0

8. Floyd–Warshall: all-pairs shortest paths

Dijkstra answers queries from one source and requires nonnegative weights. Floyd–Warshall computes all-pairs shortest paths and supports negative edges, provided the result is not affected by a negative cycle.

Initializing the distance matrix

For V vertices, build dist[V][V]:

• dist[i][i] = 0;
• dist[i][j] = weight(i, j) when an edge exists;
• dist[i][j] = INF when j is directly unreachable from i.

INF must not be Long.MAX_VALUE: adding a weight could overflow and become negative. Use the safe sentinel Long.MAX_VALUE / 4, and never add unreachable distances.

Invariant and matrix evolution

Before processing k, dist[i][j] is the best known cost whose intermediate vertices belong to 0..k-1. Each pair either keeps that cost or takes a route through k:

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

Example (∞ means unreachable), with edges A→B=4, B→C=-2, and A→C=5:

Initial             After allowing B
    A   B   C           A   B   C
A   0   4   5       A   0   4   2
B   ∞   0  -2       B   ∞   0  -2
C   ∞   ∞   0       C   ∞   ∞   0

The A→C value decreases from 5 to 2 because the A→B→C path becomes available. The entire matrix evolves once for each possible intermediate vertex.

Safe Java implementation

The method validates that its input is a square matrix, rejects null rows, out-of-range values, and empty matrices. The input uses the same INF sentinel to represent a missing edge.

public final class FloydWarshall {
    public static final long INF = Long.MAX_VALUE / 4;

    public record Result(long[][] distances, boolean hasNegativeCycle) {}

    public static Result compute(long[][] weights) {
        validateMatrix(weights);
        int vertices = weights.length;
        long[][] dist = new long[vertices][vertices];

        for (int i = 0; i < vertices; i++) {
            for (int j = 0; j < vertices; j++) {
                long weight = weights[i][j];
                dist[i][j] = i == j ? Math.min(0, weight) : weight;
            }
        }

        for (int k = 0; k < vertices; k++) {
            for (int i = 0; i < vertices; i++) {
                if (dist[i][k] == INF) continue;
                for (int j = 0; j < vertices; j++) {
                    if (dist[k][j] == INF) continue;
                    long throughK = dist[i][k] + dist[k][j];
                    if (throughK < dist[i][j]) {
                        dist[i][j] = throughK;
                    }
                }
            }
        }

        boolean negativeCycle = false;
        for (int v = 0; v < vertices; v++) {
            if (dist[v][v] < 0) {
                negativeCycle = true;
                break;
            }
        }
        return new Result(copy(dist), negativeCycle);
    }

    private static void validateMatrix(long[][] weights) {
        if (weights == null || weights.length == 0) {
            throw new IllegalArgumentException("matrix is required and cannot be empty");
        }
        int vertices = weights.length;
        for (int i = 0; i < vertices; i++) {
            if (weights[i] == null || weights[i].length != vertices) {
                throw new IllegalArgumentException("a square matrix is required");
            }
            for (long weight : weights[i]) {
                if (weight < -INF || weight > INF) {
                    throw new IllegalArgumentException("weight is outside the safe range");
                }
            }
        }
    }

    private static long[][] copy(long[][] matrix) {
        long[][] result = new long[matrix.length][];
        for (int i = 0; i < matrix.length; i++) {
            result[i] = matrix[i].clone();
        }
        return result;
    }
}

Addition is safe because two finite values, each between -INF and INF, cannot reach the limits of long. A pair remains unreachable when its cell ends at INF; it must not be printed as a real distance.

Negative edges and cycles

A negative edge is valid: it can represent credit, profit, or a cost correction. Dijkstra fails with negative edges because it finalizes a distance that a later edge could reduce. Floyd–Warshall incorporates them correctly.

A negative cycle makes it possible to reduce a cost indefinitely. After the three loops, dist[v][v] < 0 detects that v participates in such a cycle. The affected “shortest distances” are then undefined; the caller must treat hasNegativeCycle as an explicit failure rather than consuming the matrix as valid output.

Complexity and selection

Floyd–Warshall takes O(V³) time because of its three loops and O(V²) space for the matrix. It is straightforward for all pairs and works well for dense or moderately sized graphs.

Running Dijkstra from every vertex usually costs O(V · (E log V)) with adjacency lists and can be better for sparse graphs, but only when every edge is nonnegative. Representation, permitted weights, and query shape determine the algorithm; there is no universal winner.

Key takeaways

• A graph is the most general structure: a tree is a connected, acyclic graph with a chosen root.
• Adjacency list for sparse graphs (nearly all real ones); matrix only when it is dense.
• In Java the adjacency list is a Map<V, List<V>>, and computeIfAbsent does the heavy lifting.
• Without a visited Set, any cycle turns the traversal into an infinite loop.
• BFS and DFS are the same algorithm: the only difference is a queue versus a stack.
• Mark vertices visited on enqueue, never on dequeue.
• BFS gives the fewest-edges path; when edges have weight, you need Dijkstra.
• Dijkstra always visits the cheapest pending vertex and relaxes its edges. It is invalid with negative weights.