Skip to content

Commit 6a22b91

Browse files
bodiambodiam
authored
Merge pull request eugenp#7770 from dupirefr/bael-3128
dupirefr/dupire.francois+pro@gmail.com [BAEL-3128] Breadth-First Search Algorithm in Java
2 parents 2df8e9a + 223a767 commit 6a22b91

File tree

4 files changed

+205
-0
lines changed

4 files changed

+205
-0
lines changed

‎algorithms-miscellaneous-3/src/main/java/com/baeldung/algorithms/breadthfirstsearch/BreadthFirstSearchAlgorithm.java

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
package com.baeldung.algorithms.breadthfirstsearch;
2+
3+
import org.slf4j.Logger;
4+
import org.slf4j.LoggerFactory;
5+
6+
import java.util.*;
7+
8+
public class BreadthFirstSearchAlgorithm {
9+
10+
private static final Logger LOGGER = LoggerFactory.getLogger(BreadthFirstSearchAlgorithm.class);
11+
12+
public static <T> Optional<Tree<T>> search(T value, Tree<T> root) {
13+
Queue<Tree<T>> queue = new ArrayDeque<>();
14+
queue.add(root);
15+
16+
Tree<T> currentNode;
17+
while (!queue.isEmpty()) {
18+
currentNode = queue.remove();
19+
LOGGER.info("Visited node with value: {}", currentNode.getValue());
20+
21+
if (currentNode.getValue().equals(value)) {
22+
return Optional.of(currentNode);
23+
} else {
24+
queue.addAll(currentNode.getChildren());
25+
}
26+
}
27+
28+
return Optional.empty();
29+
}
30+
31+
public static <T> Optional<Node<T>> search(T value, Node<T> start) {
32+
Queue<Node<T>> queue = new ArrayDeque<>();
33+
queue.add(start);
34+
35+
Node<T> currentNode;
36+
Set<Node<T>> alreadyVisited = new HashSet<>();
37+
38+
while (!queue.isEmpty()) {
39+
currentNode = queue.remove();
40+
LOGGER.info("Visited node with value: {}", currentNode.getValue());
41+
42+
if (currentNode.getValue().equals(value)) {
43+
return Optional.of(currentNode);
44+
} else {
45+
alreadyVisited.add(currentNode);
46+
queue.addAll(currentNode.getNeighbors());
47+
queue.removeAll(alreadyVisited);
48+
}
49+
}
50+
51+
return Optional.empty();
52+
}
53+
54+
}

‎algorithms-miscellaneous-3/src/main/java/com/baeldung/algorithms/breadthfirstsearch/Node.java

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
package com.baeldung.algorithms.breadthfirstsearch;
2+
3+
import java.util.Collections;
4+
import java.util.HashSet;
5+
import java.util.Set;
6+
7+
public class Node<T> {
8+
9+
private T value;
10+
private Set<Node<T>> neighbors;
11+
12+
public Node(T value) {
13+
this.value = value;
14+
this.neighbors = new HashSet<>();
15+
}
16+
17+
public T getValue() {
18+
return value;
19+
}
20+
21+
public Set<Node<T>> getNeighbors() {
22+
return Collections.unmodifiableSet(neighbors);
23+
}
24+
25+
public void connect(Node<T> node) {
26+
if (this == node) throw new IllegalArgumentException("Can't connect node to itself");
27+
this.neighbors.add(node);
28+
node.neighbors.add(this);
29+
}
30+
31+
}

‎algorithms-miscellaneous-3/src/main/java/com/baeldung/algorithms/breadthfirstsearch/Tree.java

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
package com.baeldung.algorithms.breadthfirstsearch;
2+
3+
import java.util.ArrayList;
4+
import java.util.Collections;
5+
import java.util.List;
6+
7+
public class Tree<T> {
8+
9+
private T value;
10+
private List<Tree<T>> children;
11+
12+
private Tree(T value) {
13+
this.value = value;
14+
this.children = new ArrayList<>();
15+
}
16+
17+
public static <T> Tree<T> of(T value) {
18+
return new Tree<>(value);
19+
}
20+
21+
public T getValue() {
22+
return value;
23+
}
24+
25+
public List<Tree<T>> getChildren() {
26+
return Collections.unmodifiableList(children);
27+
}
28+
29+
public Tree<T> addChild(T value) {
30+
Tree<T> newChild = new Tree<>(value);
31+
children.add(newChild);
32+
return newChild;
33+
}
34+
}

‎algorithms-miscellaneous-3/src/test/java/com/baeldung/algorithms/breadthfirstsearch/BreadthFirstSearchAlgorithmUnitTest.java

Lines changed: 86 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,86 @@
1+
package com.baeldung.algorithms.breadthfirstsearch;
2+
3+
import org.junit.jupiter.api.Test;
4+
5+
import static org.assertj.core.api.Assertions.assertThat;
6+
7+
class BreadthFirstSearchAlgorithmUnitTest {
8+
9+
private Tree<Integer> root;
10+
private Tree<Integer> rootFirstChild;
11+
private Tree<Integer> depthMostChild;
12+
private Tree<Integer> rootSecondChild;
13+
14+
private Node<Integer> start;
15+
private Node<Integer> firstNeighbor;
16+
private Node<Integer> firstNeighborNeighbor;
17+
private Node<Integer> secondNeighbor;
18+
19+
@Test
20+
void givenTree_whenSearchTen_thenRoot() {
21+
initTree();
22+
assertThat(BreadthFirstSearchAlgorithm.search(10, root)).isPresent().contains(root);
23+
}
24+
25+
@Test
26+
void givenTree_whenSearchThree_thenDepthMostValue() {
27+
initTree();
28+
assertThat(BreadthFirstSearchAlgorithm.search(3, root)).isPresent().contains(depthMostChild);
29+
}
30+
31+
@Test
32+
void givenTree_whenSearchFour_thenRootSecondChild() {
33+
initTree();
34+
assertThat(BreadthFirstSearchAlgorithm.search(4, root)).isPresent().contains(rootSecondChild);
35+
}
36+
37+
@Test
38+
void givenTree_whenSearchFive_thenNotFound() {
39+
initTree();
40+
assertThat(BreadthFirstSearchAlgorithm.search(5, root)).isEmpty();
41+
}
42+
43+
private void initTree() {
44+
root = Tree.of(10);
45+
rootFirstChild = root.addChild(2);
46+
depthMostChild = rootFirstChild.addChild(3);
47+
rootSecondChild = root.addChild(4);
48+
}
49+
50+
@Test
51+
void givenNode_whenSearchTen_thenStart() {
52+
initNode();
53+
assertThat(BreadthFirstSearchAlgorithm.search(10, firstNeighborNeighbor)).isPresent().contains(start);
54+
}
55+
56+
@Test
57+
void givenNode_whenSearchThree_thenNeighborNeighbor() {
58+
initNode();
59+
assertThat(BreadthFirstSearchAlgorithm.search(3, firstNeighborNeighbor)).isPresent().contains(firstNeighborNeighbor);
60+
}
61+
62+
@Test
63+
void givenNode_whenSearchFour_thenSecondNeighbor() {
64+
initNode();
65+
assertThat(BreadthFirstSearchAlgorithm.search(4, firstNeighborNeighbor)).isPresent().contains(secondNeighbor);
66+
}
67+
68+
@Test
69+
void givenNode_whenSearchFive_thenNotFound() {
70+
initNode();
71+
assertThat(BreadthFirstSearchAlgorithm.search(5, firstNeighborNeighbor)).isEmpty();
72+
}
73+
74+
private void initNode() {
75+
start = new Node<>(10);
76+
firstNeighbor = new Node<>(2);
77+
start.connect(firstNeighbor);
78+
79+
firstNeighborNeighbor = new Node<>(3);
80+
firstNeighbor.connect(firstNeighborNeighbor);
81+
firstNeighborNeighbor.connect(start);
82+
83+
secondNeighbor = new Node<>(4);
84+
start.connect(secondNeighbor);
85+
}
86+
}

0 commit comments

Comments
 (0)