Graphs and Union-Find

Graphs and Union-Find

Building upon the core data structures introduced in Chapter 2—such as ArrayList for random access, LinkedList for efficient insertions, HashMap for key-value mappings, and TreeMap for ordered storage—this section extends the analytical framework to graph data structures and algorithms essential for technical interviews. Graphs model pairwise relationships between objects, ubiquitous in problems ranging from social networks to course prerequisites. Mastery involves rapid selection between adjacency list and matrix representations, implementing depth-first search (DFS) and breadth-first search (BFS) for traversal, detecting cycles, and leveraging Union-Find for connectivity queries, with justifications deliverable in under 30 seconds. Integrating Java 21+ features like Records for immutable vertices and pattern matching for state handling, this content ensures interview-ready code backed by explicit time and space complexity analysis.

Graph Representations: Adjacency List vs. Adjacency Matrix

A Graph is a data structure consisting of a set of vertices (nodes) and a set of edges (connections between vertices). In Java 21+, representing graphs efficiently hinges on choosing between adjacency list and adjacency matrix based on graph density and operation frequencies.

• Adjacency List: A graph representation using a map from each vertex to a list of its adjacent vertices, with space complexity O(V+E), where V is the number of vertices and E is the number of edges. This representation is memory-efficient for sparse graphs, as it stores only existing edges. Java’s Map<Vertex, List<Vertex>> is ideal, with Vertex implemented as a Record for immutability.

  public record Vertex(int id) {}
  public class Graph {
      private final Map<Vertex, List<Vertex>> adjList = new HashMap<>();
      public void addVertex(Vertex v) { adjList.putIfAbsent(v, new ArrayList<>()); }
      public void addEdge(Vertex from, Vertex to) { adjList.get(from).add(to); }
      // DFS iterative implementation
      public void dfs(Vertex start) {
          Set<Vertex> visited = new HashSet<>();
          Deque<Vertex> stack = new ArrayDeque<>();
          stack.push(start);
          while (!stack.isEmpty()) {
              Vertex current = stack.pop();
              if (!visited.contains(current)) {
                  visited.add(current);
                  for (Vertex neighbor : adjList.getOrDefault(current, List.of())) {
                      stack.push(neighbor);
                  }
              }
          }
      }
  }

  Time Complexity for traversal: O(V+E); Space Complexity: O(V) for visited set and stack.

• Adjacency Matrix: A graph representation using a 2D boolean array where matrix[i][j] is true if there is an edge from vertex i to j, with space complexity O(V²). This suits dense graphs or scenarios requiring O(1) edge existence queries, at the cost of higher memory overhead.

Performance trade-offs are summarized in the following complexity table:

Operation	Adjacency List	Adjacency Matrix	DFS	BFS	Union-Find
Space	O(V+E)	O(V²)	O(V)	O(V)	O(V)
Time (traversal)	O(V+E)	O(V²)	O(V+E)	O(V+E)	O(α(n)) per op

Memory layouts differ significantly: adjacency list uses a HashMap with references to ArrayList objects for each vertex, incurring overhead from object headers and pointers, while adjacency matrix employs a contiguous 2D array of booleans with fixed size based on V². Union-Find typically uses arrays for parent and rank indices, with minimal overhead per vertex. Choosing between them involves evaluating trade-offs:

Aspect	Adjacency List	Adjacency Matrix	DFS	BFS
Space Efficiency	High for sparse graphs	Low for sparse, high for dense	Moderate	Moderate
Edge Query	O(degree)	O(1)	N/A	N/A
Best Use	Sparse graphs, dynamic operations	Dense graphs, frequent edge checks	Deep traversal, cycle detection	Shortest paths, level-order

Depth-First Search and Breadth-First Search

Depth-First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking, implemented recursively or with an explicit stack. The iterative version above uses a Deque for the stack, with space complexity O(V) due to the visited set and stack. DFS is pivotal for cycle detection: in undirected graphs, it requires handling parent nodes to avoid false positives, while in directed graphs, it uses visited and recursion stack sets to identify back edges.

Breadth-First Search (BFS) explores all neighbors at the present depth before moving to the next level, implemented using a queue with space complexity O(V). BFS finds the shortest path in unweighted graphs and is ideal for level-order traversal, contrasting with DFS’s depth-oriented approach. For instance, in the “Number of Islands” problem—a common interview scenario—both DFS and BFS can traverse grid cells representing land and water, with time complexity O(V+E) where V is cells and E is adjacency edges.

Trade-offs between BFS and DFS are explicit: DFS uses less memory in best-case scenarios for deep graphs due to stack depth, but BFS is superior for shortest path problems where minimal distance is required. This aligns with the analytical comparison in the trade-off matrix.

Union-Find for Connectivity and Cycle Detection

Union-Find (Disjoint Set Union) is a data structure that maintains a collection of disjoint sets with union and find operations, optimized with union by rank and path compression to achieve amortized time complexity O(α(n)) per operation, where α is the inverse Ackermann function, and space complexity O(V). It excels in dynamic connectivity queries, such as finding connected components or detecting cycles in undirected graphs efficiently.

For example, in the “Redundant Connection” problem, Union-Find can identify edges that form cycles by checking if two vertices are already connected before unioning them. This contrasts with DFS-based cycle detection, which might be less efficient for incremental edge additions. Connected components—subgraphs where any two vertices are connected by paths—can be found using DFS or BFS in O(V+E) time, but Union-Find offers near-linear time for dynamic scenarios, making it a versatile tool in interview settings.

Practical Applications and Interview Readiness

Graph algorithms are frequently tested in interviews through problems like “Course Schedule,” which uses topological sort to detect cycles in directed graphs, and “Network Connectivity,” which leverages Union-Find for component analysis. Topological sort—a linear ordering of vertices in a directed acyclic graph such that for every directed edge u→v, u comes before v—can be performed using Kahn’s algorithm with time complexity O(V+E). Kahn’s algorithm detects cycles by failing to reduce in-degrees to zero, providing a clear failure mode for cycle detection.

To avoid common pitfalls, adhere to this failure mode checklist:

1. Not handling null inputs for vertices or edges.
2. Incorrect cycle detection logic leading to false positives or negatives.
3. Forgetting to mark vertices as visited in DFS/BFS, causing infinite loops.
4. Using String concatenation in loops for graph output, leading to O(n²) time.
5. Ignoring edge cases like empty graphs or single vertices.
6. Not analyzing time and space complexity explicitly in interviews.
7. Using platform threads unnecessarily instead of virtual threads for I/O-bound graph tasks.

Structured problem-solving is enhanced by the interview pattern template:

1. Understand the problem: Identify if it involves traversal, connectivity, cycles, or ordering.
2. Choose representation: Based on graph density and operations (adjacency list vs matrix).
3. Select algorithm: DFS for depth-oriented tasks, BFS for shortest paths, Union-Find for connectivity queries.
4. Implement in Java 21+: Use Records for data carriers, pattern matching for state handling, virtual threads if concurrent.
5. Analyze complexity: State time and space Big-O notation, considering worst-case.
6. Test edge cases: Null inputs, empty graphs, cycles, disconnected components.

This template integrates modern Java features, such as virtual threads for concurrent graph traversals in I/O-bound tasks, though synchronization must prevent thread pinning. By building on prerequisite knowledge—like the TreeNode Record from CH2-S3 for tree structures or the ImmutableList from CH2 for immutable data carriers—this section ensures continuity and depth, preparing readers to tackle graph-related challenges with precision and efficiency.