Depth first search algorithm in Java

Depth first search algorithm in Java.md

Depth first search algorithm in Java

Sample Data

For this gist, let’s consider this tree as our data.

               A <--------- |
               |            |
           B <- -> C        |
           |       |        |
           D       E        |        
           |       |        |
           F   G <- -> H -> |

Data Structure

For the sake of simplicity here is your Node class used to represent nodes in the a tree (without all the getters and setters).

public class Node {
    private ArrayList<Node> children = new ArrayList<>();
}

Implementation

Here is one implementation for depth first search that does not used a “visited” marker on the nodes. Instead it uses a list of unvisited nodes to achieve such a thing.

public List<Node> search() {
		
    List<Node> visitedNodes = new LinkedList<>();
    List<Node> unvisitedNodes = new LinkedList<>();

    unvisitedNodes.add(this);

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

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

    return visitedNodes;

}

So let’s trace what the seach if we are starting from the A node.

Step 1:

1. The values for the lists are visitedNodes = [] unvisitedNodes = [A]. Since there is an element in unvisitedNodes, we enter the loop.
2. In the loop, currNode = A.
3. We remove A from unvisitedNodes so unvisitedNodes = [].
4. We add B, C to unvisitedNode and we add them at the begining of the list so unvisitedNodes = [B, C].
5. At the end of the loop, visitedNodes = [A].

Step 2:

1. The values for the lists are visitedNodes = [A] unvisitedNodes = [B, C]. Since there are elements in unvisitedNodes, the loop continues.
2. In the loop, currNode = B.
3. We remove B from unvisitedNodes so unvisitedNodes = [C].
4. We add D to unvisitedNode and we add them at the begining of the list so unvisitedNodes = [D, C].
5. At the end of the loop, visitedNodes = [A, B].

Step 3:

1. The values for the lists are visitedNodes = [A, B] unvisitedNodes = [D, C]. Since there are elements in unvisitedNodes, the loop continues.
2. In the loop, currNode = D.
3. We remove D from unvisitedNodes so unvisitedNodes = [C].
4. We add F to unvisitedNode and we add them at the begining of the list so unvisitedNodes = [F, C].
5. At the end of the loop, visitedNodes = [A, B, D].

Step 4:

1. The values for the lists are visitedNodes = [A, B, D] unvisitedNodes = [F, C]. Since there are elements in unvisitedNodes, the loop continues.
2. In the loop, currNode = F.
3. We remove F from unvisitedNodes so unvisitedNodes = [C].
4. We don’t add any nodes here since F is a leaf, so unvisitedNodes = [C].
5. At the end of the loop, visitedNodes = [A, B, D, F].

Step 5:

1. The values for the lists are visitedNodes = [A, B, D, F] unvisitedNodes = [C]. Since there are elements in unvisitedNodes, the loop continues.
2. In the loop, currNode = C.
3. We remove C from unvisitedNodes so unvisitedNodes = [].
4. We add E to unvisitedNode and we add them at the begining of the list so unvisitedNodes = [E].
5. At the end of the loop, visitedNodes = [A, B, D, F, C].

Step 6:

1. The values for the lists are visitedNodes = [A, B, D, F, C] unvisitedNodes = [E]. Since there are elements in unvisitedNodes, the loop continues.
2. In the loop, currNode = E.
3. We remove E from unvisitedNodes so unvisitedNodes = [].
4. We add G, H to unvisitedNode and we add them at the begining of the list so unvisitedNodes = [G, H].
5. At the end of the loop, visitedNodes = [A, B, D, F, C, E].

Step 7:

1. The values for the lists are visitedNodes = [A, B, D, F, C, E] unvisitedNodes = [G, H]. Since there are elements in unvisitedNodes, the loop continues.
2. In the loop, currNode = G.
3. We remove G from unvisitedNodes so unvisitedNodes = [H].
4. We don’t add any nodes here since G is a leaf, so unvisitedNodes = [H].
5. At the end of the loop, visitedNodes = [A, B, D, F, C, E, G].

Step 8:

1. The values for the lists are visitedNodes = [A, B, D, F, C, E, G] unvisitedNodes = [H]. Since there are elements in unvisitedNodes, the loop continues.
2. In the loop, currNode = H.
3. We remove H from unvisitedNodes so unvisitedNodes = [].
4. We don’t add any nodes here since H is a not leaf but has A as a children and it has already been visited., so unvisitedNodes = [].
5. At the end of the loop, visitedNodes = [A, B, D, F, C, E, G, H].
6. We’re done.