Repository: TheAlgorithms/Java (java)

Issue:
[FEATURE REQUEST] DFS and BFS  search algorithms are lack of effective tests and Node class should be decoupled from DFS
### What would you like to Propose?

- Write DFS and BFS  search algorithms effective tests.
- Write a new Node class in structures  - its should be decoupled from the DFS class.
- Some code refactoring.
-  Support of multiple data types

### Issue details

BreadthFirstSearch.java
- add algorithm tests
- refactor
DepthFirstSearch.java

- write a new test file 
- refactor - mention that this is a recursive solution (in the future add an iterative solution as well)

### Additional Information

_No response_

Pull request:
DFS and BFS search algorithms  - Resolve #4229
<!-- For completed items, change [ ] to [x] -->

- [x] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [x] This pull request is all my own work -- I have not plagiarized it.
- [x] All filenames are in PascalCase.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.

Resolve #4229


Patch:
diff --git a/pom.xml b/pom.xml
index 82b239e4..0347ccdb 100644
--- a/pom.xml
+++ b/pom.xml
@@ -38,7 +38,9 @@
             <groupId>org.assertj</groupId>
             <artifactId>assertj-core</artifactId>
             <version>${assertj.version}</version>
+            <scope>test</scope>
         </dependency>
+
         <dependency>
             <groupId>org.junit.jupiter</groupId>
             <artifactId>junit-jupiter-api</artifactId>
diff --git a/src/main/java/com/thealgorithms/datastructures/Node.java b/src/main/java/com/thealgorithms/datastructures/Node.java
new file mode 100644
index 00000000..c8d0e6cb
--- /dev/null
+++ b/src/main/java/com/thealgorithms/datastructures/Node.java
@@ -0,0 +1,32 @@
+package com.thealgorithms.datastructures;
+
+import java.util.ArrayList;
+import java.util.List;
+
+public class Node<T> {
+
+    private final T value;
+    private final List<Node<T>> children;
+
+    public Node(final T value) {
+        this.value = value;
+        this.children = new ArrayList<>();
+    }
+
+    public Node(final T value, final List<Node<T>> children) {
+        this.value = value;
+        this.children = children;
+    }
+
+    public T getValue() {
+        return value;
+    }
+
+    public void addChild(Node<T> child) {
+        children.add(child);
+    }
+
+    public List<Node<T>> getChildren() {
+        return children;
+    }
+}
diff --git a/src/main/java/com/thealgorithms/searches/BreadthFirstSearch.java b/src/main/java/com/thealgorithms/searches/BreadthFirstSearch.java
index 99ee6c27..77043a03 100644
--- a/src/main/java/com/thealgorithms/searches/BreadthFirstSearch.java
+++ b/src/main/java/com/thealgorithms/searches/BreadthFirstSearch.java
@@ -1,32 +1,45 @@
 package com.thealgorithms.searches;
 
-import com.thealgorithms.searches.DepthFirstSearch.Node;
-import java.util.ArrayDeque;
-import java.util.Optional;
-import java.util.Queue;
+import com.thealgorithms.datastructures.Node;
+import java.util.*;
 
 /**
  * @author: caos321
  * @date: 31 October 2021 (Sunday)
+ * @wiki: https://en.wikipedia.org/wiki/Breadth-first_search
  */
-public class BreadthFirstSearch {
-    public static Optional<Node> search(final Node node, final String name) {
-        if (node.getName().equals(name)) {
+public class BreadthFirstSearch<T> {
+
+    private final List<T> visited = new ArrayList<>();
+
+    public Optional<Node<T>> search(final Node<T> node, final T value) {
+        if (node == null) {
+            return Optional.empty();
+        }
+        if (node.getValue().equals(value)) {
+            // add root node to visited
+            visited.add(value);
             return Optional.of(node);
         }
+        visited.add(node.getValue());
 
-        Queue<Node> queue = new ArrayDeque<>(node.getSubNodes());
+        Queue<Node<T>> queue = new ArrayDeque<>(node.getChildren());
 
         while (!queue.isEmpty()) {
-            final Node current = queue.poll();
+            final Node<T> current = queue.poll();
+            visited.add(current.getValue());
 
-            if (current.getName().equals(name)) {
+            if (current.getValue().equals(value)) {
                 return Optional.of(current);
             }
 
-            queue.addAll(current.getSubNodes());
+            queue.addAll(current.getChildren());
         }
 
         return Optional.empty();
     }
+
+    public List<T> getVisited() {
+        return visited;
+    }
 }
diff --git a/src/main/java/com/thealgorithms/searches/DepthFirstSearch.java b/src/main/java/com/thealgorithms/searches/DepthFirstSearch.java
index 3a12537a..781768d8 100644
--- a/src/main/java/com/thealgorithms/searches/DepthFirstSearch.java
+++ b/src/main/java/com/thealgorithms/searches/DepthFirstSearch.java
@@ -1,79 +1,32 @@
 package com.thealgorithms.searches;
 
+import com.thealgorithms.datastructures.Node;
 import java.util.ArrayList;
 import java.util.List;
-import java.util.Objects;
 import java.util.Optional;
 
 /**
  * @author: caos321
  * @date: 31 October 2021 (Sunday)
+ * @wiki: https://en.wikipedia.org/wiki/Depth-first_search
  */
-public class DepthFirstSearch {
+public class DepthFirstSearch<T> {
 
-    static class Node {
+    private final List<T> visited = new ArrayList<>();
 
-        private final String name;
-        private final List<Node> subNodes;
-
-        public Node(final String name) {
-            this.name = name;
-            this.subNodes = new ArrayList<>();
-        }
-
-        public Node(final String name, final List<Node> subNodes) {
-            this.name = name;
-            this.subNodes = subNodes;
-        }
-
-        public String getName() {
-            return name;
-        }
-
-        public List<Node> getSubNodes() {
-            return subNodes;
+    public Optional<Node<T>> recursiveSearch(final Node<T> node, final Integer value) {
+        if (node == null) {
+            return Optional.empty();
         }
-    }
-
-    public static Optional<Node> search(final Node node, final String name) {
-        if (node.getName().equals(name)) {
+        visited.add(node.getValue());
+        if (node.getValue().equals(value)) {
             return Optional.of(node);
         }
 
-        return node.getSubNodes().stream().map(value -> search(value, name)).flatMap(Optional::stream).findAny();
-    }
-
-    public static void assertThat(final Object actual, final Object expected) {
-        if (!Objects.equals(actual, expected)) {
-            throw new AssertionError(String.format("expected=%s but was actual=%s", expected, actual));
-        }
+        return node.getChildren().stream().map(v -> recursiveSearch(v, value)).flatMap(Optional::stream).findAny();
     }
 
-    public static void main(final String[] args) {
-        final Node rootNode = new Node("A", List.of(new Node("B", List.of(new Node("D"), new Node("F", List.of(new Node("H"), new Node("I"))))), new Node("C", List.of(new Node("G"))), new Node("E")));
-
-        {
-            final String expected = "I";
-
-            final Node result = search(rootNode, expected).orElseThrow(() -> new AssertionError("Node not found!"));
-
-            assertThat(result.getName(), expected);
-        }
-
-        {
-            final String expected = "G";
-
-            final Node result = search(rootNode, expected).orElseThrow(() -> new AssertionError("Node not found!"));
-
-            assertThat(result.getName(), expected);
-        }
-
-        {
-            final String expected = "E";
-
-            final Node result = search(rootNode, expected).orElseThrow(() -> new AssertionError("Node not found!"));
-
-            assertThat(result.getName(), expected);
-        }
+    public List<T> getVisited() {
+        return visited;
     }
 }


Test patch:
diff --git a/src/test/java/com/thealgorithms/searches/BreadthFirstSearchTest.java b/src/test/java/com/thealgorithms/searches/BreadthFirstSearchTest.java
index 2a5fe0b9..4c9f16d4 100644
--- a/src/test/java/com/thealgorithms/searches/BreadthFirstSearchTest.java
+++ b/src/test/java/com/thealgorithms/searches/BreadthFirstSearchTest.java
@@ -2,33 +2,101 @@ package com.thealgorithms.searches;
 
 import static org.junit.jupiter.api.Assertions.*;
 
+import com.thealgorithms.datastructures.Node;
 import java.util.List;
 import java.util.Optional;
+import org.junit.jupiter.api.BeforeEach;
 import org.junit.jupiter.api.Test;
 
-class BreadthFirstSearchTest {
+public class BreadthFirstSearchTest {
+    private Node<String> root;
+    private BreadthFirstSearch<String> bfs;
 
-    private static final DepthFirstSearch.Node rootNode = new DepthFirstSearch.Node("A",
-        List.of(new DepthFirstSearch.Node("B", List.of(new DepthFirstSearch.Node("D"), new DepthFirstSearch.Node("F", List.of(new DepthFirstSearch.Node("H"), new DepthFirstSearch.Node("I"))))), new DepthFirstSearch.Node("C", List.of(new DepthFirstSearch.Node("G"))), new DepthFirstSearch.Node("E")));
+    // Tree structure:
+    //
+    //        A
+    //      / | \
+    //     B  C  D
+    //    / \
+    //   E   F
+
+    @BeforeEach
+    public void setUp() {
+        // nodes declaration
+        root = new Node<>("A");
+
+        var nodeB = new Node<>("B");
+        var nodeC = new Node<>("C");
+        var nodeD = new Node<>("D");
+
+        var nodeE = new Node<>("E");
+        var nodeF = new Node<>("F");
+
+        // tree initialization
+        root.addChild(nodeB);
+        root.addChild(nodeC);
+        root.addChild(nodeD);
+
+        nodeB.addChild(nodeE);
+        nodeB.addChild(nodeF);
+
+        // create an instance to monitor the visited nodes
+        bfs = new BreadthFirstSearch<>();
+    }
 
     @Test
-    void searchI() {
-        Optional<DepthFirstSearch.Node> Inode = BreadthFirstSearch.search(rootNode, "I");
-        assertTrue(Inode.isPresent());
-        assertEquals(Inode.get().getName(), "I");
+    public void testSearchRoot() {
+        String expectedValue = "A";
+        List<String> expectedPath = List.of("A");
+
+        // check value
+        Optional<Node<String>> value = bfs.search(root, expectedValue);
+        assertEquals(expectedValue, value.orElse(new Node<>("")).getValue());
+
+        // check path
+        assertArrayEquals(expectedPath.toArray(), bfs.getVisited().toArray());
     }
 
     @Test
-    void searchG() {
-        Optional<DepthFirstSearch.Node> Gnode = BreadthFirstSearch.search(rootNode, "G");
-        assertTrue(Gnode.isPresent());
-        assertEquals(Gnode.get().getName(), "G");
+    public void testSearchF() {
+        String expectedValue = "F";
+        List<String> expectedPath = List.of("A", "B", "C", "D", "E", "F");
+
+        // check value
+        Optional<Node<String>> value = Optional.of(bfs.search(root, expectedValue).orElse(new Node<>(null)));
+        assertEquals(expectedValue, value.get().getValue());
+
+        // check path
+        assertArrayEquals(expectedPath.toArray(), bfs.getVisited().toArray());
     }
 
     @Test
-    void searchE() {
-        Optional<DepthFirstSearch.Node> Enode = BreadthFirstSearch.search(rootNode, "E");
-        assertTrue(Enode.isPresent());
-        assertEquals(Enode.get().getName(), "E");
+    void testSearchNull() {
+        List<String> expectedPath = List.of("A", "B", "C", "D", "E", "F");
+        Optional<Node<String>> node = bfs.search(root, null);
+
+        // check value
+        assertTrue(node.isEmpty());
+
+        // check path
+        assertArrayEquals(expectedPath.toArray(), bfs.getVisited().toArray());
+    }
+
+    @Test
+    void testNullRoot() {
+        var value = bfs.search(null, "B");
+        assertTrue(value.isEmpty());
+    }
+
+    @Test
+    void testSearchValueThatNotExists() {
+        List<String> expectedPath = List.of("A", "B", "C", "D", "E", "F");
+        var value = bfs.search(root, "Z");
+
+        // check that the value is empty because it's not exists in the tree
+        assertTrue(value.isEmpty());
+
+        // check path is the whole list
+        assertArrayEquals(expectedPath.toArray(), bfs.getVisited().toArray());
     }
 }
\ No newline at end of file
diff --git a/src/test/java/com/thealgorithms/searches/DepthFirstSearchTest.java b/src/test/java/com/thealgorithms/searches/DepthFirstSearchTest.java
new file mode 100644
index 00000000..f85e9409
--- /dev/null
+++ b/src/test/java/com/thealgorithms/searches/DepthFirstSearchTest.java
@@ -0,0 +1,91 @@
+package com.thealgorithms.searches;
+
+import static org.junit.jupiter.api.Assertions.*;
+
+import com.thealgorithms.datastructures.Node;
+import java.util.List;
+import java.util.Optional;
+import org.junit.jupiter.api.BeforeEach;
+import org.junit.jupiter.api.Test;
+
+public class DepthFirstSearchTest {
+
+    private Node<Integer> root;
+    private DepthFirstSearch<Integer> dfs;
+
+    //
+    // Tree structure:
+    //          1
+    //        / | \
+    //       2  3  4
+    //      / \
+    //     5   6
+
+    @BeforeEach
+    public void setUp() {
+        // nodes declaration
+        root = new Node<>(1);
+
+        var nodeB = new Node<>(2);
+        var nodeC = new Node<>(3);
+        var nodeD = new Node<>(4);
+
+        var nodeE = new Node<>(5);
+        var nodeF = new Node<>(6);
+
+        // tree initialization
+        root.addChild(nodeB);
+        root.addChild(nodeC);
+        root.addChild(nodeD);
+
+        nodeB.addChild(nodeE);
+        nodeB.addChild(nodeF);
+
+        // create an instance to monitor the visited nodes
+        dfs = new DepthFirstSearch<>();
+    }
+
+    @Test
+    public void testSearchRoot() {
+        Integer expectedValue = 1;
+        List<Integer> expectedPath = List.of(1);
+
+        // check value
+        Optional<Node<Integer>> value = dfs.recursiveSearch(root, expectedValue);
+        assertEquals(expectedValue, value.orElse(new Node<>(null)).getValue());
+
+        // check path
+        assertArrayEquals(expectedPath.toArray(), dfs.getVisited().toArray());
+    }
+
+    @Test
+    public void testSearch4() {
+        Integer expectedValue = 4;
+        List<Integer> expectedPath = List.of(1, 2, 5, 6, 3, 4);
+
+        // check value
+        Optional<Node<Integer>> value = dfs.recursiveSearch(root, expectedValue);
+        assertEquals(expectedValue, value.orElse(new Node<>(null)).getValue());
+
+        // check path
+        assertArrayEquals(expectedPath.toArray(), dfs.getVisited().toArray());
+    }
+
+    @Test
+    void testNullRoot() {
+        var value = dfs.recursiveSearch(null, 4);
+        assertTrue(value.isEmpty());
+    }
+
+    @Test
+    void testSearchValueThatNotExists() {
+        List<Integer> expectedPath = List.of(1, 2, 5, 6, 3, 4);
+        var value = dfs.recursiveSearch(root, 10);
+
+        // check that the value is empty because it's not exists in the tree
+        assertTrue(value.isEmpty());
+
+        // check path is the whole list
+        assertArrayEquals(expectedPath.toArray(), dfs.getVisited().toArray());
+    }
+}