Graph Traversal Algorithms in TheAlgorithms/Java: BFS and DFS Implementations

The TheAlgorithms/Java repository contains comprehensive implementations of Breadth-First Search (BFS) and Depth-First Search (DFS) algorithms, including specialized variants like 0-1 BFS, Hopcroft-Karp, Kosaraju’s algorithm, and Tarjan’s algorithm, located primarily in src/main/java/com/thealgorithms/graph/ and related packages.

The TheAlgorithms/Java repository provides a robust collection of graph traversal algorithms suitable for both educational purposes and algorithmic problem solving. These implementations cover fundamental traversal patterns as well as advanced applications such as maximum flow, bipartite matching, and strongly connected components. All classes are open-source and organized under the com.thealgorithms.graph and com.thealgorithms.datastructures.graphs packages.

BFS Implementations in TheAlgorithms/Java

The repository offers several Breadth-First Search variants, ranging from basic utilities to specialized algorithms for weighted graphs and network flow problems.

0-1 BFS for Shortest Paths

The ZeroOneBfs.java file in src/main/java/com/thealgorithms/graph/ implements the 0-1 BFS algorithm for finding shortest paths in graphs with edge weights of 0 or 1. Unlike standard BFS that uses a simple queue, this implementation utilizes a Deque to handle 0-weight edges by adding them to the front of the queue, achieving linear time complexity. The shortestPaths() method accepts the number of vertices, an adjacency list, and a source node, returning an array of minimum distances.

BFS in Maximum Flow and Matching

Several advanced algorithms leverage BFS as a foundational step:

• HopcroftKarp.java – Uses BFS to construct layered graphs for maximum bipartite matching before DFS finds augmenting paths.
• EdmondsKarp.java – Implements the Edmonds-Karp max-flow algorithm using BFS to find the shortest augmenting path in the residual network.
• Dinic.java – Employs BFS to build level graphs for the Dinic max-flow algorithm, followed by DFS for blocking flows.
• MatrixGraphs.java – Located in src/main/java/com/thealgorithms/datastructures/graphs/, this class demonstrates generic BFS traversal on adjacency matrix representations.

DFS Implementations in TheAlgorithms/Java

Depth-First Search appears throughout the repository in various forms, from constrained traversals to algorithms for topological sorting and cycle detection.

Predecessor-Constrained DFS

The PredecessorConstrainedDfs.java file provides a specialized DFS that visits nodes only after all their predecessors have been processed. This implementation emits VISIT and SKIP events, making it suitable for topological-order-aware traversals. The dfsRecursiveOrder() method accepts a successor map and starting node, returning a list of traversal events that track the discovery order.

DFS for Strongly Connected Components and Topological Sort

• Kosaraju.java – Implements Kosaraju’s two-pass algorithm: the first DFS orders vertices by finish time, and the second DFS operates on the transposed graph to identify strongly connected components (SCCs).
• TarjansAlgorithm.java – Computes SCCs in a single DFS pass using low-link values and discovery times.
• TopologicalSort.java – Located in src/main/java/com/thealgorithms/sorts/, this class uses DFS recursion stack detection to produce topological orderings and detect cycles in directed acyclic graphs (DAGs).

Specialized DFS Utilities

• BipartiteGraphDFS.java – Performs bipartite graph checking via DFS coloring in src/main/java/com/thealgorithms/datastructures/graphs/.
• HierholzerAlgorithm.java – Finds Eulerian paths and cycles using a depth-first walk that records edges during traversal.
• WordSearch.java and AllPathsFromSourceToTarget.java – Located in the backtracking package, these files demonstrate DFS applications for grid traversal and path enumeration in DAGs.

Working Code Examples

Running 0-1 BFS

import com.thealgorithms.graph.ZeroOneBfs;
import java.util.ArrayList;
import java.util.List;

public class ZeroOneBfsDemo {
    public static void main(String[] args) {
        int n = 5;                          // vertices 0 … 4
        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());

        // Edge: 0 → 1 (weight 0)
        adj.get(0).add(new int[]{1, 0});
        // Edge: 1 → 2 (weight 1)
        adj.get(1).add(new int[]{2, 1});
        // Edge: 0 → 3 (weight 1)
        adj.get(0).add(new int[]{3, 1});
        // Edge: 3 → 4 (weight 0)
        adj.get(3).add(new int[]{4, 0});

        int src = 0;
        int[] dist = ZeroOneBfs.shortestPaths(n, adj, src);
        // dist now holds [0,0,1,1,1]
        for (int i = 0; i < n; i++) {
            System.out.println("dist[" + i + "] = " + dist[i]);
        }
    }
}

Executing Predecessor-Constrained DFS

import com.thealgorithms.graph.PredecessorConstrainedDfs;
import com.thealgorithms.graph.PredecessorConstrainedDfs.TraversalEvent;
import java.util.*;

public class ConstrainedDfsDemo {
    public static void main(String[] args) {
        // Build a DAG: 0 → 1, 0 → 2, 1 → 3, 2 → 3
        Map<Integer, List<Integer>> succ = new HashMap<>();
        succ.put(0, List.of(1, 2));
        succ.put(1, List.of(3));
        succ.put(2, List.of(3));
        // No outgoing edges from 3
        succ.put(3, List.of());

        List<TraversalEvent<Integer>> events = PredecessorConstrainedDfs.dfsRecursiveOrder(succ, 0);
        for (TraversalEvent<Integer> e : events) {
            System.out.println(e);
        }
    }
}

Using Hopcroft-Karp for Bipartite Matching

import com.thealgorithms.graph.HopcroftKarp;
import java.util.*;

public class HopcroftKarpDemo {
    public static void main(String[] args) {
        // Left side vertices 0..2, right side 0..2
        int nLeft = 3, nRight = 3;
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < nLeft; i++) adj.add(new ArrayList<>());

        // Edges: L0–R0, L0–R1, L1–R1, L2–R2
        adj.get(0).addAll(List.of(0, 1));
        adj.get(1).add(1);
        adj.get(2).add(2);

        HopcroftKarp hk = new HopcroftKarp(nLeft, nRight, adj);
        int maxMatch = hk.maxMatching();
        System.out.println("Maximum matching size = " + maxMatch);
    }
}

Summary

• TheAlgorithms/Java provides comprehensive graph traversal algorithms including both BFS and DFS variants in the src/main/java/com/thealgorithms/graph/ directory.
• BFS implementations range from ZeroOneBfs for 0-1 weighted graphs to network flow algorithms like HopcroftKarp, EdmondsKarp, and Dinic that use BFS for layered graph construction.
• DFS implementations include PredecessorConstrainedDfs for dependency-aware traversal, Kosaraju and TarjansAlgorithm for strongly connected components, and HierholzerAlgorithm for Eulerian paths.
• All algorithms are implemented as reusable Java classes with clear method signatures like shortestPaths(), dfsRecursiveOrder(), and maxMatching(), suitable for integration into larger projects.

Frequently Asked Questions

Where are the graph traversal algorithms located in TheAlgorithms/Java?

The primary implementations reside in src/main/java/com/thealgorithms/graph/ for advanced algorithms like 0-1 BFS and max-flow, while fundamental data structure traversals appear in src/main/java/com/thealgorithms/datastructures/graphs/. Backtracking examples using DFS are located in src/main/java/com/thealgorithms/backtracking/.

Does TheAlgorithms/Java include both iterative and recursive DFS implementations?

Yes. The repository includes recursive DFS implementations in PredecessorConstrainedDfs.java and Kosaraju.java, while algorithms like TarjansAlgorithm.java and TopologicalSort.java also utilize recursive stack-based traversal patterns. Some utilities like HierholzerAlgorithm.java implement iterative stack-based DFS for specific use cases.

Can I use these graph traversal algorithms in production code?

While the TheAlgorithms/Java repository is primarily educational, the implementations follow standard algorithmic patterns with clear interfaces. Classes like ZeroOneBfs and HopcroftKarp provide static or instance-based methods that can be adapted for production use, though you should review edge case handling and input validation for your specific requirements.

How does the 0-1 BFS implementation differ from standard BFS in the repository?

The ZeroOneBfs.java implementation differs from standard BFS by utilizing a Deque instead of a standard queue, allowing it to push 0-weight edges to the front for immediate processing. This optimization reduces the time complexity to O(V + E) for graphs with 0-1 weights, whereas standard BFS in MatrixGraphs.java uses a simple queue and assumes unweighted graphs.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}