# How to Create and Traverse Graphs Using Guava's Graph Library

> Learn to create and traverse graphs with Guava. Use GraphBuilder and Traverser for efficient BFS and DFS graph operations.

- Repository: [Google/guava](https://github.com/google/guava)
- Tags: how-to-guide
- Published: 2026-08-08

---

**Use `GraphBuilder` to construct `MutableGraph` or `ImmutableGraph` instances, then apply `Traverser.forGraph()` or `Traverser.forTree()` to perform BFS or DFS traversals over your data structures.**

The Google Guava library provides a lightweight, type-safe graph API in the `com.google.common.graph` package that enables you to model directed and undirected graphs without external dependencies. This API supports both mutable and immutable graph implementations, offering fluent builders for construction and specialized traversers for efficient path exploration. Whether you are modeling social networks, dependency trees, or state machines, Guava's graph utilities provide the necessary tools to create and traverse complex relationships in Java.

## Understanding Guava's Graph API Architecture

Guava's graph implementation separates graph construction from traversal through distinct interfaces and builders. The architecture centers on immutable views for read operations and specialized builders for type-safe construction.

### GraphBuilder for Graph Construction

The **`GraphBuilder`** class, located in [`guava/src/com/google/common/graph/GraphBuilder.java`](https://github.com/google/guava/blob/main/guava/src/com/google/common/graph/GraphBuilder.java), provides a fluent API for configuring graph properties before instantiation. You initiate construction by selecting directionality—`GraphBuilder.directed()` or `GraphBuilder.undirected()`—then chain configuration methods such as `allowsSelfLoops(true)`, `nodeOrder(ElementOrder.insertion())`, or `expectedNodeCount(int)` to optimize internal data structures.

### MutableGraph vs ImmutableGraph

Guava distinguishes between modifiable and unmodifiable graph instances through two core interfaces:

- **`MutableGraph`** ([`guava/src/com/google/common/graph/MutableGraph.java`](https://github.com/google/guava/blob/main/guava/src/com/google/common/graph/MutableGraph.java)): Extends the base `Graph` interface with mutating operations including `addNode(N node)` and `putEdge(N nodeU, N nodeV)`. Use this when your graph structure changes at runtime.
- **`ImmutableGraph`** ([`guava/src/com/google/common/graph/ImmutableGraph.java`](https://github.com/google/guava/blob/main/guava/src/com/google/common/graph/ImmutableGraph.java)): An unmodifiable snapshot created via `GraphBuilder.immutable()` followed by `build()`. Once constructed, attempts to modify the graph throw `UnsupportedOperationException`.

### The Graph Interface

The base **`Graph`** interface ([`guava/src/com/google/common/graph/Graph.java`](https://github.com/google/guava/blob/main/guava/src/com/google/common/graph/Graph.java)) exposes read-only views through methods like `nodes()`, `edges()`, `adjacentNodes(node)`, `predecessors(node)`, and `successors(node)`. All returned collections are live, unmodifiable views backed by the underlying graph structure, ensuring consistency while preventing external modification.

## Creating Graphs with GraphBuilder

To create a graph in Guava, instantiate the appropriate builder type, configure optional constraints, and populate the structure with nodes and edges.

### Building a Mutable Undirected Graph

For graphs requiring runtime modifications, use `GraphBuilder` with `build()` to obtain a `MutableGraph` instance:

```java
import com.google.common.graph.*;

public class MutableGraphExample {
  public static void main(String[] args) {
    // Configure an undirected graph that allows self-loops
    MutableGraph<String> graph = GraphBuilder.undirected()
        .allowsSelfLoops(true)
        .nodeOrder(ElementOrder.insertion())
        .expectedNodeCount(10)
        .build();

    // Populate the graph
    graph.putEdge("bread", "bread");          // self-loop
    graph.putEdge("bread", "chocolate");
    graph.putEdge("chocolate", "peanut butter");
    graph.putEdge("peanut butter", "jelly");

    // Query the graph structure
    System.out.println("Nodes: " + graph.nodes());
    System.out.println("Successors of 'bread': " + graph.successors("bread"));
  }
}

```

### Building an Immutable Directed Graph

For static graph structures, use the immutable builder pattern to create a thread-safe, memory-efficient snapshot:

```java
import com.google.common.graph.*;

public class ImmutableGraphExample {
  public static void main(String[] args) {
    // Start with a directed immutable builder
    ImmutableGraph.Builder<String> builder = GraphBuilder.<String>directed()
        .allowsSelfLoops(false)
        .immutable();

    // Add edges (returns builder for chaining)
    builder.putEdge("a", "b")
           .putEdge("a", "c")
           .putEdge("b", "d")
           .putEdge("c", "d")
           .putEdge("d", "e");

    // Build the immutable graph
    ImmutableGraph<String> dag = builder.build();

    // Access read-only views
    System.out.println("Predecessors of 'd': " + dag.predecessors("d"));
  }
}

```

## Traversing Graphs with Traverser

The **`Traverser`** class ([`guava/src/com/google/common/graph/Traverser.java`](https://github.com/google/guava/blob/main/guava/src/com/google/common/graph/Traverser.java)) provides generic graph traversal algorithms without requiring manual stack or queue management. You obtain a `Traverser` instance through static factory methods that accept a successor function.

### BFS and DFS Traversal Methods

`Traverser` exposes three primary traversal orders, each returning an `Iterable` that lazily evaluates nodes as you iterate:

- **`breadthFirst(startNode)`**: Explores nodes in breadth-first search (BFS) order, visiting all neighbors at the present depth before moving deeper.
- **`depthFirstPreOrder(startNode)`**: Performs depth-first search (DFS), yielding nodes immediately upon first encounter.
- **`depthFirstPostOrder(startNode)`**: Performs DFS but yields nodes only after visiting all descendants, useful for dependency resolution.

### General Graphs vs Tree Structures

Guava provides two factory methods depending on your graph's structural guarantees:

- **`Traverser.forGraph(successorsFunction)`**: Use for general graphs where cycles may exist. The traverser tracks visited nodes to ensure each reachable node is visited **at most once**, preventing infinite loops in cyclic structures.
- **`Traverser.forTree(successorsFunction)`**: Use for tree or forest structures (DAGs where each node has exactly one path from the root). This implementation assumes no cycles and visits each node **exactly once**, offering slightly better performance by eliminating visited-set overhead.

Both traversal methods run in **O(n)** time and **O(n)** space, where *n* is the number of reachable nodes, using the node's `equals()` and `hashCode()` methods for identity checks.

### Traversal Code Examples

The following example demonstrates BFS and DFS traversals on a general undirected graph:

```java
import com.google.common.graph.*;

public class GraphTraversalExample {
  public static void main(String[] args) {
    MutableGraph<String> graph = GraphBuilder.undirected()
        .allowsSelfLoops(true)
        .build();

    graph.putEdge("bread", "bread");
    graph.putEdge("bread", "chocolate");
    graph.putEdge("chocolate", "peanut butter");
    graph.putEdge("peanut butter", "jelly");

    // Create traverser for general graphs (handles cycles)
    Traverser<String> traverser = Traverser.forGraph(graph::successors);

    System.out.println("BFS from 'bread':");
    for (String node : traverser.breadthFirst("bread")) {
      System.out.println(node);
    }

    System.out.println("\nDFS pre-order from 'bread':");
    for (String node : traverser.depthFirstPreOrder("bread")) {
      System.out.println(node);
    }
  }
}

```

For tree-like directed acyclic graphs (DAGs), use the tree-specific traverser:

```java
import com.google.common.graph.*;

public class TreeTraversalExample {
  public static void main(String[] args) {
    ImmutableGraph<String> dag = GraphBuilder.<String>directed()
        .immutable()
        .putEdge("a", "b")
        .putEdge("a", "c")
        .putEdge("b", "d")
        .putEdge("c", "d")
        .putEdge("d", "e")
        .build();

    // Optimized for tree structures (no cycle checking overhead)
    Traverser<String> treeTraverser = Traverser.forTree(dag::successors);

    System.out.println("DFS post-order (tree) from 'a':");
    for (String node : treeTraverser.depthFirstPostOrder("a")) {
      System.out.println(node);
    }
  }
}

```

## Working with Graph Utilities

The **`Graphs`** utility class ([`guava/src/com/google/common/graph/Graphs.java`](https://github.com/google/guava/blob/main/guava/src/com/google/common/graph/Graphs.java)) provides static helper methods for common graph operations. Use `Graphs.hasEdgeConnecting(graph, nodeU, nodeV)` to check edge existence, `Graphs.degree(graph, node)` to calculate total degree, or `Graphs.transitiveClosure(graph)` to compute the transitive closure of a directed graph. These utilities operate on any `Graph` implementation, allowing you to analyze both mutable and immutable instances without manual iteration logic.

## Summary

- Use **`GraphBuilder`** to configure directionality, self-loop policies, and node ordering before instantiating graphs.
- Choose **`MutableGraph`** for dynamic structures that change at runtime, or **`ImmutableGraph`** for static, thread-safe snapshots created through `GraphBuilder.immutable()`.
- Access graph topology through the **`Graph`** interface methods `nodes()`, `successors()`, `predecessors()`, and `adjacentNodes()`.
- Employ **`Traverser.forGraph()`** for cyclic graphs or **`Traverser.forTree()`** for DAGs to perform BFS, DFS pre-order, or DFS post-order traversals.
- Leverage the **`Graphs`** utility class for common operations like edge checking and transitive closure calculations.
- All traversal operations guarantee **O(n)** time complexity and visit each node at most once (for general graphs) or exactly once (for trees).

## Frequently Asked Questions

### What's the difference between MutableGraph and ImmutableGraph?

**`MutableGraph`** allows runtime modifications through methods like `addNode()` and `putEdge()`, while **`ImmutableGraph`** creates an unmodifiable snapshot via `GraphBuilder.immutable().build()`. Once built, immutable graphs throw `UnsupportedOperationException` on modification attempts, providing thread safety and memory efficiency for static graph structures.

### How do I handle cycles when traversing a Guava graph?

Use **`Traverser.forGraph()`** instead of `Traverser.forTree()` when your graph may contain cycles. The `forGraph()` implementation maintains an internal set of visited nodes to ensure each node is processed at most once, preventing infinite loops during traversal. According to the source code in [`Traverser.java`](https://github.com/google/guava/blob/main/Traverser.java), this approach guarantees **O(n)** time complexity even with cyclic structures.

### Can I use custom objects as nodes in Guava graphs?

Yes, Guava graphs accept any object type as nodes, provided they implement proper **`equals()`** and **`hashCode()`** contracts. The graph implementation uses these methods for identity checks during edge insertion and traversal. For best performance with large graphs, ensure your node objects are immutable and have efficient hash code implementations.

### What performance characteristics does Guava's Traverser provide?

Both `Traverser.forGraph()` and `Traverser.forTree()` provide **O(n)** time and **O(n)** space complexity, where *n* represents the number of reachable nodes from the starting node. The traverser lazily evaluates nodes as you iterate the returned `Iterable`, minimizing memory overhead. Tree traversals offer slightly better constant factors since they skip the visited-set checks required for general graphs.