DZone
Thanks for visiting DZone today,
Edit Profile
  • Manage Email Subscriptions
  • How to Post to DZone
  • Article Submission Guidelines
Sign Out View Profile
  • Post an Article
  • Manage My Drafts
Over 2 million developers have joined DZone.
Log In / Join
Please enter at least three characters to search
Refcards Trend Reports
Events Video Library
Refcards
Trend Reports

Events

View Events Video Library

Zones

Culture and Methodologies Agile Career Development Methodologies Team Management
Data Engineering AI/ML Big Data Data Databases IoT
Software Design and Architecture Cloud Architecture Containers Integration Microservices Performance Security
Coding Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
Culture and Methodologies
Agile Career Development Methodologies Team Management
Data Engineering
AI/ML Big Data Data Databases IoT
Software Design and Architecture
Cloud Architecture Containers Integration Microservices Performance Security
Coding
Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance
Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks

The software you build is only as secure as the code that powers it. Learn how malicious code creeps into your software supply chain.

Apache Cassandra combines the benefits of major NoSQL databases to support data management needs not covered by traditional RDBMS vendors.

Generative AI has transformed nearly every industry. How can you leverage GenAI to improve your productivity and efficiency?

Modernize your data layer. Learn how to design cloud-native database architectures to meet the evolving demands of AI and GenAI workloads.

Related

  • Exploring TakeWhile and DropWhile Functions in Java
  • Using Java Stream Gatherers To Improve Stateful Operations
  • Thread-Safety Pitfalls in XML Processing
  • Java Stream API: 3 Things Every Developer Should Know About

Trending

  • Caching 101: Theory, Algorithms, Tools, and Best Practices
  • Data Lake vs. Warehouse vs. Lakehouse vs. Mart: Choosing the Right Architecture for Your Business
  • The Perfection Trap: Rethinking Parkinson's Law for Modern Engineering Teams
  • Immutable Secrets Management: A Zero-Trust Approach to Sensitive Data in Containers
  1. DZone
  2. Coding
  3. Java
  4. Implementing DFS and BFS With Java 8 Streams

Implementing DFS and BFS With Java 8 Streams

Streams present a more functional approach to searching and collecting nodes, allowing you to easily implement depth and breadth-first searching.

By 
Niklas Wuensche user avatar
Niklas Wuensche
·
Jan. 04, 17 · Tutorial
Likes (13)
Comment
Save
Tweet
Share
35.1K Views

Join the DZone community and get the full member experience.

Join For Free

Searching through graphs and trees is one of the standard problems of every programmer. Not least because it is a standard job interview question. And as I read and watched a lot about functional programming in Java 8, I considered to write an implementation of the BFS and the DFS with the help of streams. For this post, you should already know what a BFS and DFS looks like.

Prerequisites

Before we start with the implementation of the algorithms, we need a class for the nodes. I will use a binary tree here, but you can adapt the algorithms to any kind of graph/tree.

Java
 
public class Node {

    private Node left;
    private Node right;
    private String label;

    public Node(@NotNull String label, @Nullable Node left, @Nullable Node right) {
        this.left = left;
        this.right = right;
        this.label = label;
    }

    @Override
    public String toString() {
        return label;
    }

    public List<Node> getChildren() {
        return Stream.of(left, right)
                .filter(Objects::nonNull)
                .collect(Collectors.toList());
    }

}


(Thanks to Alexey Polyakov for pointing out that I can simplify getChildren())

This is the node class. Every note has zero, one or two childs. If a child should not exist, you can set it to null in the construcutor. The label helps with the identification later on. We can see the first use of a stream in the getChildren() method. If you can’t imagine what a stream looks like, then imagine a list with some extra features.

First of, we create a List of the left and right child node. We stream this list to use the filter method on it. The reason we want to filter is that we do not want to give null nodes back. They would cause NullPointerExceptions later on. In the end, we store(collect) everything in a List and give it back.

Depth First Search (DFS)

Now, let’s talk about the DFS. We want a method which takes a root and returns a list of all nodes it finds, in the order of a DFS.

Java
 
public class Node {

    //...

    public List<Node> searchByDepth() {
        List<Node> visitedNodes = new LinkedList<>();
        List<Node> unvisitedNodes = new LinkedList<>();
        unvisitedNodes.add(this);

        while(!unvisitedNodes.isEmpty()) {
            Node currNode = unvisitedNodes.remove(0);

            List<Node> newNodes = currNode.getChildren()
                    .stream()
                    .filter(node -> !visitedNodes.contains(node))
                    .collect(Collectors.toList());

            unvisitedNodes.addAll(0, newNodes);
            visitedNodes.add(currNode);
        }

        return visitedNodes;
    }

}


Let me explain this snippet. We have two lists. We store the nodes which we already visited in the visitedNode list and the unvisited in the unvistedNotes list. Before we start the real DFS, we have to add the root of the graph, which is the node this method was called on, to the unvisitedNotes.

Now, we have to visited every reamining node that we have not visited. That’s what the loop is good for. We take the first node that we have not visited from the list. Then we stream over the list of child nodes. We want to filter out every node that we already visited (to eliminate circles) and collect it again in a list.

Here you can also see why the number of children is irrelevant for the algorithm to work. The number of child nodes could be 1, 3 or any number, you just have to give back a different number of notes in the getChildren() method.

Now we have a list of new nodes that we can reach from the current node and which we haven’t visited already. Next up, we add these nodes in the beginning of our unvisited nodes list. We do this, because we want to go deeper into the graph (that’s the reason we use a DFS �� ) We visited the currentNode, so we can add it to the list of visited nodes. When there is no unvisited node left, and so we visited all reachable nodes, we return the list of visitedNodes.

And this was the DFS with the help of streams. I like this functional way a lot more than the imperative one. It increases the readability of the code.

Breadth First Search (BFS)

Next of, the snippet of the BFS.

Java
 
public class Node {

    //...

    public List<Node> searchByBreadth() {
        List<Node> visitedNodes = new LinkedList<>();
        List<Node> unvisitedNodes = Arrays.asList(this);

        while(!unvisitedNodes.isEmpty()) {
            List<Node> newNodes = unvisitedNodes
                    .stream()
                    .map(Node::getChildren)
                    .flatMap(List::stream)
                    .filter(node -> !visitedNodes.contains(node))
                    .collect(Collectors.toList());

            visitedNodes.addAll(unvisitedNodes);
            unvisitedNodes = newNodes;
        }

        return visitedNodes;
    }

}


As you can see, the beginning of the BFS is the same as the one of the DFS. But as you know, we search for new nodes by the layers of the graph, not node after node (this would be the idea of the DFS). The idea of the BFS is that we search the child nodes of the next layer for all nodes of the current layer. That’s the reason we can work over the whole list of unvisitedNodes, not just over the first node of the list.

We use map to create a new stream which contains all the child notes of all the unvisitedNodes. This new stream is of type Stream<List<Nodes>>, because getChildren() returns a list of nodes. If you are not familliar with this notation:

Java
 
.map(Node::getChildren)


is the same as:

Java
 
.map(node -> node.getChildren()) .


But we want to have a stream of nodes, not a stream of list of nodes. That’s the reason we use flatMap. It creates a stream of every list and connects all these new stream to one big one. So Stream<List<Nodes>> becomes Stream<Nodes> again. These are the nodes of the next layer. The filter does the same as in the DFS. Every node that was visited before will be filtered out.

And in the end, we collect a List<Nodes> out of Stream<Nodes> and store them in a newNodeslist, like in the DFS example. We have visited all notes of the current layer. That’s the reason we add all of them to the visitedNodes. The new notes we found are the unvistedNodes of the next iteration. We do this as long as we find new nodes.

When we collected all visited nodes, we can stop the loop and return the list of visited nodes. We added the Nodes in this list layer by layer, so it has the sorting of a BFS.

Conclusion

Working with streams can improve your code quality a lot. They help you to split a big task into many small ones, which you can solve one at a time. I like functional programming and Haskell in particular. The way that Java 8 goes with Lambdas, Streams and Optionals is IMHO a good step and a lot of imperative algorithms can be decluttered with the help of them.

Would you like to read more about functional programming in Java? Should I also write an introduction for it? And what do you think about the DFS and BFS in Java 8? Here is a Gist with the working code.

Thank you for reading and have a nice day,

Niklas

Stream (computing) Java (programming language) Functional programming

Published at DZone with permission of Niklas Wuensche, DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

Related

  • Exploring TakeWhile and DropWhile Functions in Java
  • Using Java Stream Gatherers To Improve Stateful Operations
  • Thread-Safety Pitfalls in XML Processing
  • Java Stream API: 3 Things Every Developer Should Know About

Partner Resources

×

Comments
Oops! Something Went Wrong

The likes didn't load as expected. Please refresh the page and try again.

ABOUT US

  • About DZone
  • Support and feedback
  • Community research
  • Sitemap

ADVERTISE

  • Advertise with DZone

CONTRIBUTE ON DZONE

  • Article Submission Guidelines
  • Become a Contributor
  • Core Program
  • Visit the Writers' Zone

LEGAL

  • Terms of Service
  • Privacy Policy

CONTACT US

  • 3343 Perimeter Hill Drive
  • Suite 100
  • Nashville, TN 37211
  • support@dzone.com

Let's be friends:

Likes
There are no likes...yet! 👀
Be the first to like this post!
It looks like you're not logged in.
Sign in to see who liked this post!