Last active
July 24, 2021 05:30
-
-
Save NWuensche/c5d54b650620491b73a30514d3200269 to your computer and use it in GitHub Desktop.
DFS and BFS in Java 8 style
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import com.sun.istack.internal.NotNull; | |
import com.sun.istack.internal.Nullable; | |
import java.util.Arrays; | |
import java.util.LinkedList; | |
import java.util.List; | |
import java.util.function.Predicate; | |
import java.util.stream.Collectors; | |
/** | |
* @author Niklas Wünsche | |
*/ | |
public class SearchWithStreams { | |
public static void main(String[] args) { | |
Node root = Node.createTree(); | |
System.out.println("Nodes by DFS: ".concat(root.searchByDepth().toString())); | |
System.out.println("Nodes by BFS: ".concat(root.searchByBreadth().toString())); | |
} | |
} | |
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()); | |
} | |
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; | |
} | |
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; | |
} | |
public static Node createTree() { | |
Node right = new Node("right", null, null); | |
Node childOfLeft = new Node("child of left", null, null); | |
Node left = new Node("left", childOfLeft, null); | |
return new Node("root", left, right); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment