Introduction

Directed graphs model one-way relationships such as task dependencies, web links, and message flows. In Java, the most practical starting point is usually an adjacency-list representation, because it supports traversal algorithms efficiently without requiring a heavy framework.

Representing a Directed Graph

An adjacency list stores each node together with the nodes it points to. In Java, a Map from vertex to neighbor list is a clean baseline.

1import java.util.*;
2
3public class DirectedGraph {
4    private final Map<String, List<String>> edges = new HashMap<>();
5
6    public void addVertex(String v) {
7        edges.putIfAbsent(v, new ArrayList<>());
8    }
9
10    public void addEdge(String from, String to) {
11        addVertex(from);
12        addVertex(to);
13        edges.get(from).add(to);
14    }
15
16    public List<String> neighbors(String v) {
17        return edges.getOrDefault(v, List.of());
18    }
19
20    public Set<String> vertices() {
21        return edges.keySet();
22    }
23}

This structure is enough for many graph-processing tasks, including traversal, cycle detection, and topological sorting.

Breadth-First Search

Breadth-first search, or BFS, is useful when you want the shortest path in an unweighted directed graph or you want to explore nodes level by level.

1import java.util.*;
2
3public static List<String> bfs(DirectedGraph graph, String start) {
4    List<String> order = new ArrayList<>();
5    Queue<String> queue = new ArrayDeque<>();
6    Set<String> visited = new HashSet<>();
7
8    queue.add(start);
9    visited.add(start);
10
11    while (!queue.isEmpty()) {
12        String current = queue.remove();
13        order.add(current);
14
15        for (String next : graph.neighbors(current)) {
16            if (visited.add(next)) {
17                queue.add(next);
18            }
19        }
20    }
21
22    return order;
23}

Because the graph is directed, BFS follows only outgoing edges. If there is an edge from A to B, that does not imply the reverse path exists.

Topological Sort for Dependency Graphs

One of the most important directed-graph operations is topological sorting. It works only for directed acyclic graphs and produces an order where each node appears after its prerequisites.

1import java.util.*;
2
3public static List<String> topologicalSort(DirectedGraph graph) {
4    Map<String, Integer> indegree = new HashMap<>();
5    for (String v : graph.vertices()) {
6        indegree.putIfAbsent(v, 0);
7        for (String next : graph.neighbors(v)) {
8            indegree.put(next, indegree.getOrDefault(next, 0) + 1);
9        }
10    }
11
12    Queue<String> queue = new ArrayDeque<>();
13    for (Map.Entry<String, Integer> entry : indegree.entrySet()) {
14        if (entry.getValue() == 0) {
15            queue.add(entry.getKey());
16        }
17    }
18
19    List<String> result = new ArrayList<>();
20    while (!queue.isEmpty()) {
21        String current = queue.remove();
22        result.add(current);
23
24        for (String next : graph.neighbors(current)) {
25            int value = indegree.get(next) - 1;
26            indegree.put(next, value);
27            if (value == 0) {
28                queue.add(next);
29            }
30        }
31    }
32
33    if (result.size() != graph.vertices().size()) {
34        throw new IllegalStateException("Graph contains a cycle");
35    }
36
37    return result;
38}

This is the algorithm behind many build systems and workflow schedulers.

Example Usage

1public static void main(String[] args) {
2    DirectedGraph graph = new DirectedGraph();
3    graph.addEdge("compile", "test");
4    graph.addEdge("test", "package");
5    graph.addEdge("package", "deploy");
6
7    System.out.println(bfs(graph, "compile"));
8    System.out.println(topologicalSort(graph));
9}

For this graph, a valid topological order is:

[compile, test, package, deploy]

When to Use a Library

If you only need a few algorithms, a small in-house representation is fine. If you need shortest paths, centrality, graph export formats, or many algorithm variants, a library such as JGraphT can save time.

Still, understanding the adjacency-list model matters because most libraries are exposing the same underlying ideas.

Common Pitfalls

The most common mistake is forgetting directionality. If your code adds only from -> to, then traversals will not move backward unless you also add the reverse edge explicitly.

Another issue is ignoring cycles in dependency-style problems. Topological sort requires an acyclic graph. If a cycle exists, there is no valid dependency order and the algorithm should signal failure.

A third pitfall is using recursion carelessly for deep graphs. Recursive depth-first search is elegant, but very deep graphs may risk stack overflow. An explicit stack is safer for large or adversarial inputs.

Finally, do not choose an adjacency matrix by default. Matrices are useful for dense graphs, but most application graphs are sparse, and adjacency lists are usually far more space-efficient.

Summary

• Directed graphs model one-way relationships and are naturally represented with adjacency lists.
• BFS explores outward through directed edges and is useful for reachability and unweighted shortest paths.
• Topological sort solves ordering problems on directed acyclic graphs.
• Always account for edge direction and cycle handling.
• Start with a simple Java representation unless your problem genuinely needs a graph library.