Java Stream API : Implementing Depth-First Search Algorithm

Implementing Depth-First Search Algorithm for Graph Traversal Using Java Stream API

Graph traversal is a fundamental algorithmic problem that involves visiting all the nodes of a graph. Depth-First Search (DFS) is one of the methods to traverse a graph, where you start from a specific node and then recursively visit its neighbors in a depthward motion before moving on to the next neighbor. In this blog post, we will explore how to implement the DFS algorithm for graph traversal using the Java Stream API.

Java Stream API : Implementing Depth-First Search Algorithm

Graph Representation

First, let's define a simple graph representation using an adjacency list. We will use a `Map` to represent the graph, where the keys are the nodes and the values are lists of adjacent nodes.

import java.util.*;

public class Graph {

    private Map<Integer, List<Integer>> adjacencyList;

    public Graph(int vertices) {

        adjacencyList = new HashMap<>();

        for (int i = 0; i < vertices; i++) {

            adjacencyList.put(i, new LinkedList<>());

        }

    }

    public void addEdge(int source, int destination) {

        adjacencyList.get(source).add(destination);

    }

    public List<Integer> getNeighbors(int vertex) {

        return adjacencyList.get(vertex);

    }

    public int getVertexCount() {

        return adjacencyList.size();

    }

}

---

advertisement

---

Depth-First Search Algorithm

Now, let's implement the DFS algorithm using the Java Stream API. The basic idea of DFS is to start from a given node, mark it as visited, and then recursively visit all its neighbors that have not been visited yet.

import java.util.*;

public class DepthFirstSearch {

    public static void main(String[] args) {

        Graph graph = new Graph(5);

        graph.addEdge(0, 1);

        graph.addEdge(0, 2);

        graph.addEdge(1, 3);

        graph.addEdge(1, 4);

        graph.addEdge(2, 4);

        dfs(graph, 0);

    }

    public static void dfs(Graph graph, int start) {

        Set<Integer> visited = new HashSet<>();

        dfsRecursive(graph, start, visited);

    }

    private static void dfsRecursive(Graph graph, int current, Set<Integer> visited) {

        visited.add(current);

        System.out.println("Visiting node: " + current);

        graph.getNeighbors(current).stream()

            .filter(neighbor -> !visited.contains(neighbor))

            .forEach(neighbor -> dfsRecursive(graph, neighbor, visited));

    }

}

In this implementation, we start the DFS traversal from node 0. The `dfsRecursive` method marks the current node as visited, prints its value, and then recursively calls itself on all unvisited neighbors of the current node.

---

advertisement

---

Conclusion

In this blog post, we explored how to implement the Depth-First Search algorithm for graph traversal using the Java Stream API. The Stream API provides a concise and expressive way to work with collections, making the implementation of algorithms like DFS more readable and maintainable.